Resolvability in graphs and the metric dimension of a graph

For an ordered subset W = (w(1),w(2),...,w(lambda)) of vertices in a connected graph G and a vertex v Of G, the metric representation of v with respect to W is the k-vector r(v \ W) = (d(v,w(1)), d(v, w(2)),...,d(v,w lambda)), The set W is a resolving set for G if r(u \ W) = r(v \ W) implies that u = v for all pairs u,v of vertices of G. The metric dimension dim(G) of G is the minimum cardinality of a resolving set for G. Bounds on dim(G) are presented in terms of the order and the diameter of G. All connected graphs of order n having dimension 1,n - 2, or n - 1 are determined. A new proof for the dimension of a tree is also presented. From this result sharp, bounds on the metric dimension of unicyclic graphs are established. It is shown that dim(H)less than or equal to dim(H x K-2)less than or equal to dim(H) + 1 for every connected graph H. Moreover, it is shown that for every positive real number epsilon, there exists a connected graph G and a connected induced subgraph H of G such that dim(G)/dim(H) < epsilon. (C) 2000 Elsevier Science B.V. All rights reserved.