Computing the metric dimension of crossed prism

Let G = (V;E) be a connected graph and let @(u; v) denote the distance between vertices u and v. A subset W of V (G) is called a resolving set for G if for everyu; v 2 V (G), there exists w 2 W such that @(u;w) 6= @(v;w). The minimum cardinality of a resolving set for G is called the metric dimension of G and is denoted by dim(G).This invariant has extensive applications in robotics, since the metric dimension can represent the minimum number of landmarks, which uniquely determine the position of a robot moving in a graph space. Finding the metric dimension of a graph is a hard problem. We present exact value of the metric dimension of crossed prism CP(n) for each n 8.

Keywords:

metric dimension , resolving set , robotics , crossed prism