On lower bounds for the metric dimension of graphs

Document Type : Research Paper

Author

Department of Science, Shahreza Campus, University of Isfahan, Isfahan, Iran

Abstract

‎For an ordered set W={w1‎,‎w2,…,wk} of vertices and a‎ vertex v in a connected graph G‎, ‎the ordered  k-vector‎ ‎r(v|W)=(d(v,w1),d(v,w2),…,d(v,wk)) is called the‎ ‎(metric) representation of v with respect to W‎, ‎where d(x,y)‎ ‎is the distance between the vertices x and y‎. ‎The set W is‎ ‎called a resolving set for G if distinct vertices of G have‎ ‎distinct representations with respect to W‎. ‎The minimum‎ ‎cardinality of a resolving set for G is its metric dimension‎, ‎and a resolving set of minimum cardinality is a basis of G‎. ‎Lower bounds for metric dimension are important‎. ‎In this paper‎, ‎we investigate lower bounds for metric dimension‎. ‎Motivated by a lower bound for the metric dimension k of a graph‎ ‎of order n with diameter d in [S‎. ‎Khuller‎, ‎B‎. ‎Raghavachari‎, ‎and‎ ‎A‎. ‎Rosenfeld‎, ‎Landmarks in graphs‎, ‎Discrete Applied Mathematics‎ ‎70(3)(1996)217−229]‎, ‎which states that k≥n−dk‎, ‎we characterize‎ all graphs‎ ‎with this lower bound and obtain a new lower bound‎. ‎This new bound is better than the previous one‎, ‎for graphs with diameter more than 3‎.

Keywords

References

[1] R.C. Brigham, G. Chartrand, R.D. Dutton, and P. Zhang, On the dimension of trees, Discrete Mathematics 294 (2005) 279-283.
[2] G.G. Chappell, J. Gimbel, and C. Hartman, Bounds on the metric and partition dimensions of a graph, Ars Combinatoria 88 (2008) 349-366.
[3] G. Chartrand, L. Eroh, M.A. Johnson, and O.R. Ollermann, Resolvability in graphs and the metric dimension of a graph, Discrete Applied Mathematics 105 (2000) 99-113.
[4] M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NO-Completeness, Freeman, New York, 1979.
[5] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combinatoria 2 (1976) 191-195.
[6] B.L. Hulme, A.W. Shiver, and P.J. Slater, A Boolean algebraic analysis of  re protection, Algebraic and Combinatorial Methods in Operations Research, 95 (1984) 215-227.
[7] M.A. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, Journal of Biopharmaceutical Statistics 3 (1993) 217-229.
[8] S. Khuller, B. Raghavachari, and A. Rosenfeld, Landmarks in graphs, Discrete Applied Mathematics 70(3) (1996) 217-229.
[9] R.A. Melter, I. Tomescu, Metric bases in digital geometry, Computer Vision, Graphics, and Image Processing, 25 (1984), 113-121.
[10] P.J. Slater, Leaves of trees, Congressus Numerantium 14 (1975) 549-559.

Files

History

  • Receive Date: 03 March 2022
  • Revise Date: 25 May 2022
  • Accept Date: 30 May 2022

Share

How to cite

Statistics