Closed formulae for the metric dimension of rooted product graphs
Ismael G. Yero, Juan Alberto Rodriguez-Velazquez, Dorota Kuziak · arXiv (Cornell University) · 2013
For an ordered subset W = {w1, w2, . . . wk} of vertices and a vertex u in a connected graph G, the representation of u with respect to W is the ordered k-tuple r(u|W ) = (d(v,w1), d(v,w2), . . . , d(v,wk)), where d(x, y) represents the distance between the vertices x and y. The set W is a metric generator for G if every two different vertices of G have distinct representations. A minimum metric generator is called a metric basis for G and its cardinality the metric dimension of G. It is well known that the problem of finding the metric dimension of a graph is NP-Hard. In this paper we obtain closed formulae for the metric dimension of rooted product graphs.