In graph theory, the metric dimension of a graph G is the minimum cardinality of a subset S of vertices 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.
Detailed definition For an ordered subset W = { w 1 , w 2 , … , w k } {\displaystyle 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 ) , … , d ( v , w k ) ) {\displaystyle 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 (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. Resolving sets for graphs were introduced independently by Slater (1975) and Harary & Melter (1976), while the concept of a resolving set and that of metric dimension were defined much earlier in the more general context of metric spaces by Blumenthal in his monograph Theory and Applications of Distance Geometry. Graphs are special examples of metric spaces with their intrinsic path metric.
Trees If a tree is a path, its metric dimension is one. Otherwise, let L denote the set of leaves, degree-one vertices in the tree. 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. The same algorithm is valid for the line graph of the tree, and thus any tree and its line graph have the same metric dimension.
Properties In Chartrand et al. (2000), it is proved that:
The metric dimension of a graph G is 1 if and only if G is a path. The metric dimension of an n-vertex graph is n − 1 if and only if it is a complete graph. The metric dimension of an n-vertex graph is n − 2 if and only if the graph is a complete bipartite graph Ks, t, a split graph K s + K t ¯ ( s ≥ 1 , t ≥ 2 ) {\displaystyle K_{s}+{\overline {K_{t}}}(s\geq 1,t\geq 2)} , or K s + ( K 1 ∪ K t ) ( s , t ≥ 1 ) {\displaystyle K_{s}+(K_{1}\cup K_{t})(s,t\geq 1)} .
… excerpt ends here. Continue reading the full article.
