On lower bounds for the metric dimension of graphs

‎For an ordered set W=\{w_۱‎, ‎w_۲,\ldots,w_k\} of vertices and a‎ vertex v in a connected graph G‎, ‎the ordered  k-vector‎ ‎r(v|W)=(d(v,w_۱),d(v,w_۲),\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‎ ‎۷۰(۳) (۱۹۹۶) ۲۱۷-۲۲۹]‎, ‎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 ۳‎.

Keywords:

Resolving set , Metric dimension , Metric basis , Lower bound , Diameter