on lower bounds for the metric dimension of graphs

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. a set w is called a resolving set for g if distinct vertices of g have distinct representations with respect to w . the minimum car-dinality 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 di-mension 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.