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

Reviewer: Ioan Tomescu (Bucureşti)

PDF
BibTeX
XML
Cite

\textit{G. Chartrand} et al., Discrete Appl. Math. 105, No. 1--3, 99--113 (2000; Zbl 0958.05042)

Full Text:
DOI

### Online Encyclopedia of Integer Sequences:

Triangle read by rows: T(n,k) is the number of (unlabeled) connected graphs with n nodes and metric dimension k, 0 <= k < n.### 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 |

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.