zbMATH — the first resource for mathematics

The metric dimension of unicyclic graphs. (English) Zbl 0990.05040
Given a graph \(G\), the representation of a vertex \(v\) with respect to an ordered set \(W=\{w_1, \dots , w_k\}\) of vertices is the \(k\)-vector \((d(v,w_1), \dots, d(v,w_k))\) of distances. If distinct vertices of \(G\) have distinct representations with respect to \(W\), then \(W\) is said to be resolving. The minimum cardinality of a resolving set is called the metric dimension of \(G\), \(\dim(G)\). P. J. Slater [Leaves of trees, Congr. Numerantium 14, 549-559 (1975; Zbl 0316.05102)] and F. Harary and R. A. Melter [Ars Comb. 1976, No. 2, 191-195 (1976; Zbl 0349.05118)] determined this invariant for trees. In this paper, tight bounds for \(\dim(G)\) are given in the case of unicyclic graphs \(G\).

05C12 Distance in graphs