Graphs with the edge metric dimension smaller than the metric dimension

被引：37

作者：

Knor, Martin ^{[1
]}

Majstorovic, Snjezana ^{[2
]}

Toshi, Aoden Teo Masa

Skrekovski, Riste ^{[3
,4
]}

Yero, Ismael G. ^{[5
]}

机构：

[1] Slovak Univ Technol Bratislava, Bratislava, Slovakia

[2] Univ Osijek, Dept Math, Osijek, Croatia

[3] Univ Ljubljana, FMF, Ljubljana 1000, Slovenia

[4] Fac Informat Studies, Novo Mesto 8000, Slovenia

[5] Univ Cadiz, Dept Matemat, Algeciras, Spain

来源：

APPLIED MATHEMATICS AND COMPUTATION | 2021年 / 401卷

关键词：

Edge metric dimension; Metric dimension; Unicyclic graphs;

D O I：

10.1016/j.amc.2021.126076

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Given a connected graph G, the metric (resp. edge metric) dimension of G is the cardinality of the smallest ordered set of vertices that uniquely identifies every pair of distinct vertices (resp. edges) of G by means of distance vectors to such a set. In this work, we settle three open problems on (edge) metric dimension of graphs. Specifically, we show that for every r, t >= 2 with r not equal t, there is n(0), such that for every n >= n(0) there exists a graph G of order n with metric dimension rand edge metric dimension t, which among other consequences, shows the existence of infinitely many graph whose edge metric dimension is strictly smaller than its metric dimension. In addition, we also prove that it is not possible to bound the edge metric dimension of a graph G by some constant factor of the metric dimension of G. (C) 2021 Elsevier Inc. All rights reserved.

引用

页数：7

共 13 条

[1]

Blumenthal L., 1953, Theory and applications of distance geometry.

[2] Edge Metric Dimension of Some Generalized Petersen Graphs [J].