Metric dimension (graph theory)
From Wikipedia, the free encyclopedia
In graph theory, the metric dimension of a graph G is the minimum number of vertices in a subset S of G such that all other vertices are uniquely determined by their distances to the vertices in S. 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 (or locating 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 (or reference set) for G.
[edit] Trees
Slater (1975) provides the following simple characterization of the metric dimension of a tree. If the tree is a path, its metric dimension is one. Otherwise, let L denote the set of degree-one vertices in the tree (usually called leaves, although Slater uses that word differently). Let K be the set of vertices that have degree greater than two, and that are connected by paths of degree-two vertices to one or more leaves. Then the metric dimension is |L| − |K|. A basis of this cardinality may be formed by removing from L one of the leaves associated with each vertex in K.
[edit] References
- Buczkowski, P.; Chartrand, G.; Poisson, C.; Zhang, P. (2003), "On k-dimensional graphs and their bases", Periodica Mathematica Hungarica 46 (1): 9–15, doi:, MR1975342.
- Chartrand, G.; Eroh, L.; Johnson, M. A.; Oellermann, O. R. (2000), "Resolvability in graphs and the metric dimension of a graph", Discrete & Applied Mathematics 105 (1–3): 99–113, doi:, MR1780464.
- Harary, F.; Melter, R. A. (1976), "On the metric dimension of a graph", Ars Combinatoria 2: 191–195, MR0457289.
- Slater, P. J. (1975), "Leaves of trees", Proc. 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), Congressus Numerantium, 14, Winnipeg: Utilitas Math., pp. 549–559, MR0422062.
- Slater, P. J. (1988), "Dominating and reference sets in a graph", Journal of Mathematical and Physical Sciences 22 (4): 445–455, MR0966610.
- Khuller, S.; Raghavachari, B.; Rosenfeld, A. (1994), Localization in graphs, Technical Report UMIACS-TR-94-92, University of Maryland, UMIACS, http://www.lib.umd.edu/drum/bitstream/1903/655/1/CS-TR-3326.ps.
- Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5 A1.5: GT61, p. 204.
.svg){kind=small}
