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)) ≥ ... + 1 for t ≥ 5, where the equality holds if and only if t = 5 and n = 13. Thus dim(Cn(1, 2, ..., t)) ≥ ... + 2 for t ≥ 6. This bound is sharp for every t ≥ 6. [ABSTRACT FROM AUTHOR]