On the Partition Dimension of Circulant Graphs

Abstract

For a vertex $v$ of a connected graph $G(V,E)$ and a subset $S$ of $V$, the distance between $v$ and $S$ is defined by $d(v,S)=min\{d(v,x):x\in S\}.$ For an ordered \emph{k}-partition $\Pi =\{S_1,S_2\dots S_k\}$ of $V$, the representation of $v$ with respect to $\Pi$ is the $k$-vector $r(v|\Pi )=(d(v,S_1),d(v,S_2)\dots d(v,S_k)).$ The $k$-partition $\Pi$ is a resolving partition if the $k$-vectors $r(v|\Pi )$, $v\in V$ are distinct. The minimum $k$ for which there is a resolving $k$-partition of $V$ is the \emph{partition dimension} of $G$. Salman et al.{\rm\cite{SaJaCh12}} claimed that \emph{partition dimension} of a class of circulant graphs $C(n,\pm \{1,2\})$, for all even $n\ge 6$ is 4 and it is 3 when $n$ is odd. In this paper we obtain the partition dimension of circulant graphs $G=C(n,\pm \{1,2\dots j\}),1\le j<\lfloor \frac{n}{2}\rfloor$, $n\ge (j+k)(j+1)$, $n\equiv kmod(2j)$ and $k$ and $2j$ are co-primes as, \begin{eqnarray*} pd(G) &=& j+1 \ \ \ \ \ \ \ when \ j \ \ is \ even \ and\ all \ k=2m-1, 1 \leq m \leq j \\ pd(G)&=& j+1\ \ \ \ \ \ \ when \ j \ \ is \ odd \ and\ all \ k=2m, 1 \leq m \leq j. \end{eqnarray*}

An error in the paper