On the partition dimension of a class of circulant graphs

For a vertex v of a connected graph G(V , E) and a subset S of V , the distance between a vertex v and S is defined by d(v, S) = min{d(v, x): x ∈ S}. For an ordered k-partition π = {S1, S2 . . . S k } of V , the partition representation of v with respect to π is the k-vector r(v|π ) = (d(v, S1), d(v, S2) . . . d(v, S k)). The k-partition π is a resolving partition if the k-vectors r(v|π ), v ∈ V (G) are distinct. The minimum k for which there is a resolving k-partition of V is the partition dimension of G. Salman et al. in their paper which appeared in Acta Mathematica Sinica, English Series proved that partition dimension of a class of circulant graph G(n, ±{1, 2}), for all even n  6 is four. In this paper we prove that it is three.

© 2014 Elsevier B.V. All rights reserved