On lower bounds for the metric dimension of graphs

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

• resolving set
• metric dimension
• metric basis
• lower bound
• diameter