Metric Dimension and Diameter in Bipartite Graphs

被引：3

作者：

Dankelmann, Peter ^{[1
]}

Morgan, Jane ^{[2
]}

Rivett-Carnac, Emily ^{[1
]}

机构：

[1] Univ Johannesburg, Johannesburg, South Africa

[2] Univ KwaZulu Natal, Durban, South Africa

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2023年 / 43卷 / 02期

关键词：

metric dimension; resolving set; diameter; maximum degree; bipartite graph; RESOLVABILITY;

D O I：

10.7151/dmgt.2382

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a connected graph and W a set of vertices of G. If every vertex of G is determined by its distances to the vertices in W, then W is said to be a resolving set. The cardinality of a minimum resolving set is called the metric dimension of G. In this paper we determine the maximum number of vertices in a bipartite graph of given metric dimension and diameter. We also determine the minimum metric dimension of a bipartite graph of given maximum degree.

引用

收藏

页码：487 / 498

页数：12

相关论文

共 14 条

[1] BOUNDING THE ORDER OF A GRAPH USING ITS DIAMETER AND METRIC DIMENSION: A STUDY THROUGH TREE DECOMPOSITIONS AND VC DIMENSION [J].

Beaudou, Laurent ;

Dankelmann, Peter ;

Foucaud, Florent ;

Henning, Michael A. ;

Mary, Arnaud ;

Parreau, Aline .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (02) :902-918

[2] 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

[3] Resolvability and the upper dimension of graphs [J].

Chartrand, G ;

Poisson, C ;

Zhang, P .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2000, 39 (12) :19-28

[4] A Comparison between the Metric Dimension and Zero Forcing Number of Trees and Unicyclic Graphs [J].

Eroh, Linda ;

Kang, Cong X. ;

Yi, Eunjeong .

ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2017, 33 (06) :731-747

[5] Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds [J].

Foucaud, Florent ;

Mertzios, George B. ;

Naserasr, Reza ;

Parreau, Aline ;

Valicov, Petru .

THEORETICAL COMPUTER SCIENCE, 2017, 668 :43-58

[6]

Harary R. A., 1976, Ars Comb, V2, P191

[7]

Hernando C, 2010, ELECTRON J COMB, V17

[8] Landmarks in graphs [J].

Khuller, S ;

Raghavachari, B ;

Rosenfeld, A .

DISCRETE APPLIED MATHEMATICS, 1996, 70 (03) :217-229

[9] COMPUTING THE METRIC DIMENSION OF A GRAPH FROM PRIMARY SUBGRAPHS [J].

Kuziak, Dorota ;

Rodriguez-Velazquez, Juan A. ;

Yero, Ismael G. .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2017, 37 (01) :273-293

[10] Comparing the metric and strong dimensions of graphs [J].

Moravcik, Gaia ;

Oellermann, Ortrud R. ;

Yusim, Samuel .

DISCRETE APPLIED MATHEMATICS, 2017, 220 :68-79