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

Chartrand, Gary; Eroh, Linda; Johnson, Mark A.; Oellermann, Ortrud R.

Discrete Appl. Math. 105, No. 1-3, 99-113 (2000).

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

Reviewer: Ioan Tomescu (Bucureşti)

MSC:

05C12	Distance in graphs
05C05	Trees

Keywords:

distance; diameter; metric dimension; tree; Cartesian product; unicyclic graph; basis

References:

[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