Resolvability in graphs and the metric dimension of a graph. (English) Zbl 0958.05042

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\).


05C12 Distance in graphs
05C05 Trees
Full Text: DOI


[1] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[2] Harary, F.; Melter, R. A., On the metric dimension of a graph, Ars Combin., 2, 191-195 (1976) · Zbl 0349.05118
[4] Slater, P. J., Leaves of trees, Congr. Numer., 14, 549-559 (1975)
[5] Slater, P. J., Dominating and reference sets in a graph, J. Math. Phys. Sci., 22, 445-455 (1988) · Zbl 0656.05057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.