Resolvability in graphs and the metric dimension of a graph (Q1582071)

For an ordered set \(W=\{w_{1},\ldots ,w_{k}\}\) 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}),\ldots ,d(v,w_{k}))\). The set \(W\) is said to be 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\). In this paper 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 and 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)\leq \dim(H\times K_{2})\leq \dim(H)+1\) for every connected graph \(H\). Moreover, it is shown that for every positive real number \(\varepsilon \), there exists a connected graph \(G\) and a connected induced subgraph \(H\) of \(G\) such that \(\dim(G)/\dim(H)<\varepsilon\).