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=\{w_1‎, ‎w_2,\ldots,w_k\}$ of vertices and a‎ vertex $v$ in a connected graph $G$‎, ‎the ordered  $k$-vector‎ ‎$r(v|W)=(d(v,w_1),d(v,w_2),\ldots,d(v,w_k))$ 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 \geq n-d^k$‎, ‎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