Geodesic
Metric dimension and diameter in bipartite graphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 487-498 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: metric dimension, resolving set, diameter, maximum degree, bipartite graph 
@article{DMGT_2023_43_2_a11,
     author = {Dankelmann, Peter and Morgan, Jane and Rivett-Carnac, Emily},
     title = {Metric dimension and diameter in bipartite graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {487--498},
     year = {2023},
     volume = {43},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a11/}
}
TY  - JOUR
AU  - Dankelmann, Peter
AU  - Morgan, Jane
AU  - Rivett-Carnac, Emily
TI  - Metric dimension and diameter in bipartite graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 487
EP  - 498
VL  - 43
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a11/
LA  - en
ID  - DMGT_2023_43_2_a11
ER  - 
%0 Journal Article
%A Dankelmann, Peter
%A Morgan, Jane
%A Rivett-Carnac, Emily
%T Metric dimension and diameter in bipartite graphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 487-498
%V 43
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a11/
%G en
%F DMGT_2023_43_2_a11
Dankelmann, Peter; Morgan, Jane; Rivett-Carnac, Emily. Metric dimension and diameter in bipartite graphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 487-498. http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a11/

[1] L. Beaudou, P. Dankelmann, F. Foucaud, M.A. Henning, A. Mary and A. Parreau, Bounding the order of a graph using its diameter and metric dimension: A study through tree decompositions and VC dimension, SIAM J. Discrete Math. 32 (2018) 902–918. https://doi.org/10.1137/16M1097833

[2] G. Chartrand, L. Eroh, M. Johnson and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000) 99–113. https://doi.org/10.1016/S0166-218X(00)00198-0

[3] G. Chartrand, G. Poisson and P. Zhang, Resolvability and the upper dimension of graphs, Comput. Math. Appl. 39 (2000) 20–28. https://doi.org/10.1016/S0898-1221(00)00126-7

[4] L. Eroh, C.X. Kang and E. Yi, A comparison between the metric dimension and zero-forcing number of trees and unicylic graphs, Acta Math. Sin. (Engl. Ser.) 33 (2017) 731–747. https://doi.org/10.1007/s10114-017-4699-4

[5] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195.

[6] F. Foucaud, G.B. Mertzios, R. Naserasr, A. Parreau and P. Valicov, Identification, location-domination and metric dimension on interval and permutation graphs: I.} Bounds, Theoret. Comput. Sci. 668 (2017) 43–58. https://doi.org/10.1016/j.tcs.2017.01.006

[7] C. Hernando, M. Mora, I.M. Pelayo, C. Seara and D.R. Wood, Extremal graph theory for metric dimension and diameter, Electron. J. Combin. 17 (2010) #R30. https://doi.org/10.37236/302

[8] S. Khuller, B. Raghavachari and A. Rosenfield, Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217–229. https://doi.org/10.1016/0166-218X(95)00106-2

[9] D. Kuziak, J.A. Rodríguez-Velázquez and I.G. Yero, Computing the metric dimension of graphs from primary subgraphs, Discuss. Math. Graph Theory 37 (2017) 273–293. https://doi.org/10.7151/dmgt.1934

[10] G. Moravcik, O.R. Oellermann and S. Yusim, Comparing the metric and strong dimensions of a graph, Discrete Appl. Math. 220 (2017) 68–79. https://doi.org/10.1016/j.dam.2016.12.020

[11] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.

[12] T. Vetrík, The metric dimension of circulant graphs, Canad. Math. Bull. 60 (2017) 206–216. https://doi.org/10.4153/CMB-2016-048-1

[13] T. Vetrík, On the metric dimension of directed and undirected circulant graphs, Discuss. Math. Graph Theory 40 (2020) 67–76. https://doi.org/10.7151/dmgt.2110

[14] I.G. Yero, D. Kuziak and J.A. Rodríguez-Velázquez, On the metric dimension of corona product graphs, Comput. Math. Appl. 61 (2011) 2793–2798. https://doi.org/10.1016/j.camwa.2011.03.046