The metric dimension of circulant graphs

A pair of vertices \(x\) and \(y\) in a graph \(G\) are said to be resolved by a vertex \(w\) if the distance from \(x\) to \(w\) is not equal to the distance from \(y\) to \(w\). We say that \(G\) is resolved by a subset of its vertices \(W\) if every pair of vertices in \(G\) is resolved by some vertex in \(W\). The minimum cardinality of a resolving set for \(G\) is called the metric dimension of \(G\), denoted by \((G)\). The circulant graph \(C_n(1,2,…,t)\) is the Cayley graph \(Cay(Z_n:\{± 1, ± 2, …, ± t\})\). In this note we prove that, for \(n=2kt+2t\), \((C_n(1,2,…,t))≥ t+2\), confirming Conjecture 4.1.2 in [K. Chau, S. Gosselin, The metric dimension of circulant graphs and their Cartesian products, Opuscula Math. 37 (2017), 509-534].