1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Metric Dimension and Diameter in Bipartite Graphs

Published Online: 21 Jan 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 14 Aug 2020
Accepted: 06 Nov 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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

MSC 2010

[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. doi:10.1137/16M109783310.1137/16M1097833Search in Google Scholar

[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. doi:10.1016/S0166-218X(00)00198-010.1016/S0166-218X(00)00198-0Search in Google Scholar

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

[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. doi:10.1007/s10114-017-4699-410.1007/s10114-017-4699-4Search in Google Scholar

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

[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. doi:10.1016/j.tcs.2017.01.00610.1016/j.tcs.2017.01.006Search in Google Scholar

[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. doi:10.37236/30210.37236/302Search in Google Scholar

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

[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. doi:10.7151/dmgt.193410.7151/dmgt.1934Search in Google Scholar

[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. doi:10.1016/j.dam.2016.12.02010.1016/j.dam.2016.12.020Search in Google Scholar

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

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

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

[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. doi:10.1016/j.camwa.2011.03.04610.1016/j.camwa.2011.03.046Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo