Nonlocal Metric Dimension of Graphs

被引：5

作者：

Klavzar, Sandi ^{[1
,2
,3
]}

Kuziak, Dorota ^{[4
]}

机构：

[1] Univ Ljubljana, Fac Math & Phys, Ljubljana, Slovenia

[2] Univ Maribor, Fac Nat Sci & Math, Maribor, Slovenia

[3] Inst Math Phys & Mech, Ljubljana, Slovenia

[4] Univ Cadiz, Dept Estadist & Invest Operat, Algeciras, Spain

来源：

BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY | 2023年 / 46卷 / 02期

关键词：

Metric dimension; Nonlocal metric dimension; Block graphs; Corona product of graphs; Edge cover number; PRODUCT;

D O I：

10.1007/s40840-022-01459-x

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Nonlocal metric dimension dimnt(G) of a graph G is introduced as the cardinality of a smallest nonlocal resolving set, that is, a set of vertices which resolves each pair of nonadjacent vertices of G. Graphs G with dim(nl)(G) = 1 or with dim(nl)(G) = n(G) - 2 are characterized. The nonlocal metric dimension is determined for block graphs, for corona products, and for wheels. Two upper bounds on the nonlocal metric dimension are proved. An embedding of an arbitrary graph into a supergraph with a small nonlocal metric dimension and small diameter is presented.

引用

页数：14

共 20 条

[1] Local metric dimension for with small numbers [J].

Abrishami, Gholamreza ;

Henning, Michael A. ;

Tavakoli, Mostafa .

DISCRETE MATHEMATICS, 2022, 345 (04)

[2] The Local Metric Dimension of the Lexicographic Product of Graphs [J].

Barragan-Ramirez, Gabriel A. ;

Estrada-Moreno, Alejandro ;

Ramirez-Cruz, Yunior ;

Rodriguez-Velazquez, Juan A. .

BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2019, 42 (05) :2481-2496

[3] The Local Metric Dimension of Strong Product Graphs [J].

Barragan-Ramirez, Gabriel A. ;

Rodriguez-Velazquez, Juan A. .

GRAPHS AND COMBINATORICS, 2016, 32 (04) :1263-1278

[4]

Buczkowski P. S., 2003, Period. Math. Hung., V46, P9, DOI [10.1023/A:1025745406160, DOI 10.1023/A:1025745406160]

[5]

Tillquist RC, 2021, Arxiv, DOI arXiv:2104.07201

[6] Resolvability in graphs and the metric dimension of a graph [J].

Chartrand, G ;

Eroh, L ;

Johnson, MA ;

Oellermann, OR .

DISCRETE APPLIED MATHEMATICS, 2000, 105 (1-3) :99-113

[7]

Fancy VF, 2017, J COMB INF SYST SCI, V42, P179

[8]

Harary F., 1976, ARS Comb, P191

[9] A linear time algorithm for metric dimension of cactus block graphs [J].

Hoffmann, Stefan ;

Elterman, Alina ;

Wanke, Egon .

THEORETICAL COMPUTER SCIENCE, 2016, 630 :43-62

[10]

Iswadi H., 2011, Far East Journal of Mathematical Sciences, V52, P155

← 1 2 →