
The metric dimension of circulant graphs
A subset $W$ of the vertex set of a graph $G$ is called a resolving
set of $G$ if for every pair of distinct vertices $u, v$ of $G$,
there is $w \in W$ such that the~distance of $w$ and $u$ is different
from the distance of $w$ and $v$. The~cardinality of a~smallest
resolving set is called the metric dimension of $G$, denoted
by $dim(G)$. The circulant graph $C_n (1, 2, \dots , t)$ consists
of the vertices $v_0, v_1, \dots , v_{n1}$ and the~edges $v_i
v_{i+j}$, where $0 \le i \le n1$, $1 \le j \le t$ $(2 \le t
\le \lfloor \frac{n}{2} \rfloor)$, the indices are taken modulo
$n$. Grigorious et al. [On the metric dimension of circulant
and Harary graphs, Applied Mathematics and Computation 248 (2014),
4754] proved that $dim(C_n (1,2, \dots , t))
\ge t+1$ for $t \lt \lfloor \frac{n}{2} \rfloor$, $n \ge 3$, and they
presented a~conjecture saying that $dim(C_n (1,2, \dots , t))
= t+p1$ for $n=2tk+t+p$, where $3 \le p \le t+1$. We disprove
both statements. We show that if $t \ge 4$ is even, there exists
an infinite set of values of $n$ such that $dim(C_n (1,2, \dots
, t)) = t$. We also prove that $dim(C_n (1,2, \dots , t)) \le
t + \frac{p}{2}$ for $n=2tk+t+p$, where $t$ and $p$ are even,
$t \ge 4$, $2 \le p \le t$ and $k \ge 1$.
Keywords:metric dimension, resolving set, circulant graph, Cayley graph, distance Categories:05C35, 05C12 