Article in volume
Authors:
Title:
Metric dimension and diameter in bipartite graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(2) (2023) 487-498
Received: 2020-08-14 , Revised: 2020-11-06 , Accepted: 2020-11-06 , Available online: 2020-12-14 , https://doi.org/10.7151/dmgt.2382
Abstract:
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
References:
- 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 - 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 - 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 - 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 - F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191–195.
- 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 - 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 - 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 - 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 - 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 - P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.
- 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 - 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 - 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
Close