On the Metric Dimension of Circulant Graphs with $2$ Generators


L. du Toit, T. Vetrík




A set of vertices $W$ resolves a connected graph $G$ if every vertex of $G$ is uniquely determined by its vector of distances to the vertices in $W$. The~number of vertices in a smallest resolving set is called the metric dimension and it is denoted by $\dim(G)$. We study the~circulant graphs $C_n (2,3)$ with the vertices $v_0, v_1, v_2,\dots, v_{n-1}$ and the edges $v_i v_{i+2}, v_i v_{i+3}$, where $i = 0, 1, 2,\dots, n-1$, the indices are taken modulo $n$. We show that for $n \ge 26$ we have $\dim(C_n (2,3)) = 3$ if $n \equiv 4 \pmod 6$, $\dim(C_n (2,3)) = 4$ if $n \equiv 0, 1, 5 \pmod 6$ and $3 \le \dim (C_n(2,3)) \le 4$ if $n \equiv 2, 3 \pmod 6$.