Sharp lower bounds on the metric dimension of circulant graphs

For n ≥ 2t + 1 where t ≥ 1, the circulant graph Cn(1, 2, . . . , t) consists of the vertices v0, v1, v2, . . . , vn−1 and the edges vivi+1, vivi+2, . . . , vivi+t, where i = 0, 1, 2, . . . , n − 1, and the subscripts are taken modulo n. We prove that the metric dimension dim(Cn(1, 2, . . . , t)) ≥ |2t/3| + 1 for t ≥ 5, where the equality holds if and only if t = 5 and n = 13. Thus dim(Cn(1, 2, . . . , t)) ≥ |2t/3| + 2 for t ≥ 6. This bound is sharp for every t ≥ 6.