Metric dimension (graph theory)

From Wikipedia, the free encyclopedia

In graph theory, the metric dimension of a graph G is the minimum cardinality of a resolving set for G. Finding the metric dimension of a graph is an NP-hard problem; the decision version, determining whether the metric dimension is less than a given value, is NP-complete.

[edit] Detailed definition

For an ordered subset W = {w₁, w₂,..., w_k} of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the ordered k-tuple r(v|W) = (d(v,w₁), d(v,w₂),...,d(v,w_k)), where d(x,y) represents the distance between the vertices x and y. The set W is a resolving set for G if every two vertices of G have distinct representations. The metric dimension of G is the minimum cardinality of a resolving set for G. A resolving set containing a minimum number of vertices is called a basis for G.

[edit] References

P. Buczkowski, G.Chartrand, C. Poisson, P. Zhang, On k-dimensional graphs and their bases, Periodica Mathematica Hungaria Vol. 46 (1), pp. 9-15, 2003.

G. Chartrand, Eroh, M. Johnson and O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math. 105, pp. 99-113, 2000.

F. Harary and R. A. Melter, On the metric dimension of a graph. Ars Combinatoria 2, pp. 191-195, 1976.

P. J. Slater, Leaves of trees. Congress. Numer. 14, pp. 549-559, 1975.

P. J. Slater, Dominating and reference sets in graphs. J. Math. Phys. Sci. 22, pp. 445-455, 1988.

Khuller, S., Raghavachari, B., and Rosenfeld, A., Localization in graphs, Technical Report UMIACS-TR-94-92, University of Maryland, UMIACS, 1994.

Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A1.5: GT61, pg.204.