The metric dimension of the circulant graph with 2k generators can be less than k

Circulant graphs are useful networks because of their symmetries. For k⩾2 and n⩾2k+1, the circulant graph C_n(1,2,…,k) consists of the vertices v₀,v₁,v₂,…,v_n-1 and the edges v_iv_i+1,v_iv_i+2,…,v_iv_i+k, where i=0,1,2,…,n-1, and the subscripts are taken modulo n. The metric dimension β(C_n(1,2,…,k)) of the circulant graphs C_n(1,2,…,k) for general k (and n) has been studied in several papers. In 2017, Chau and Gosselin proved that β(C_n(1,2,…,k))⩾k for every k, and they conjectured that if n=2k+r, where k is even and 3⩽r⩽k-1, then β(C_n(1,2,…,k))=k. We disprove both by showing that for every k⩾9, there exists an n∈[2k+5,2k+8]⊂[2k+3,3k-1] such that [Formula presented]. We conjecture that for k⩾6,β(C_n(1,2,…,k)) cannot be less than [Formula presented].