DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

P. Dankelmann

Peter Dankelmann

University of Johannesburg

email: pdankelmann@uj.ac.za

M.J. Morgan

Jane Morgan

University of KwaZulu-Natal

email: MorganJ@ukzn.ac.za

E.J. Rivett-Carnac

Emily Rivett-Carnac

University of Johannesburg

email: emilyjcarnac@gmail.com

Title:

Metric dimension and diameter in bipartite graphs

PDF

Source:

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:

  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

Close