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 
of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the ordered k-tuple 
, 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.
