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_1, w_2,\dots 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_1), d(v,w_2),\dots,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.


This combinatorics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../m/e/t/Metric_dimension_%28graph_theory%29.html"