On the Metric Dimension of Directed and Undirected Circulant Graphs

The undirected circulant graph $C_n(±1, ±2, . . ., ±t)$ consists of vertices $v_0, v_1, . . ., v_{n−1}$ and undirected edges $v_iv_{i+j}$, where $0 ≤ i ≤ n − 1, 1 ≤ j ≤ t (2 ≤ t ≤ \frac{n}{2})$, and the directed circulant graph $C_n(1, t)$ consists of vertices $v_0, v_1, . . ., v_{n−1}$ and directed edges $v_iv_{i+1}, v_iv_{i+t}$, where $0 ≤ i ≤ n − 1 (2 ≤ t ≤ n−1)$, the indices are taken modulo $n$. Results on the metric dimension of undirected circulant graphs $C_n(±1, ±t)$ are available only for special values of $t$. We give a complete solution of this problem for directed graphs $C_n(1, t)$ for every $t ≥ 2$ if $n ≥ 2t^2$. Grigorious et al. [On the metric dimension of circulant and Harary graphs, Appl. Math. Comput. 248 (2014) 47–54] presented a conjecture saying that dim $(C_n(±1, ±2, . . ., ±t)) = t + p − 1$ for $n = 2tk + t + p$, where $3 ≤ p ≤ t + 1$. We disprove it by showing that dim $(C_n(±1, ±2, . . ., ±t)) ≤ t + \frac{p+1}{2}$ for $n = 2tk + t + p$, where $t ≥ 4$ is even, $p$ is odd, $1 ≤ p ≤ t + 1$ and $k ≥ 1$.