Resolvability in graphs and the metric dimension of a graph Original Research Article

For an ordered subset W={w1,w2,…,wk} 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,w1), d(v,w2),…,d(v,wk)). 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)⩽dim(H×K2)⩽dim(H)+1 for every connected graph H. Moreover, it is shown that for every positive real number ε, there exists a connected graph G and a connected induced subgraph H of G such that dim(G)/dim(H)<ε.