The metric dimension of circulant graphs and their Cartesian products

Let G = (V, E) be a connected graph (or hypergraph) and let d(x,y) denote the distance between vertices x,y ∈V(G). A subset W ⊆V(G) is called a resolving set for G if for every pair ol distinct vertices x, y ∈ (G), there is w ∈W such that d(x,w) ≠d(y,w). The minimum cardinality of a resolving set for G is called the metric dimension of G, denoted by β (G). The circulant graph Cn(l, 2,... , t) has vertex set {v0, v1 …, vn-1} and edges [formula] where 0 ≤ i ≤ n — 1 and 1 ≤j ≤ t and the indices are taken modulo [formula]. In this paper we determine the exact metric dimension olthe circulant graphs Cn(l, 2,... , t). extending previous results due to Borchert and Gosselin (2013), Grigorious et al. (2014), and Vetrik (2016). In particular, we show that [formula] for large enough n, which implies that the metric dimension ol these circulants is completely determined by the congruence class ol n modulo 2t. We determine the exact value of β Cn (l, 2,.. . , i)) for n ≡ 2 mod 2t and n =≡ (t + 1) mod 2t and we give better bounds on the metric dimension ol these circulants for n ≡ 0 mod 2t and n ≡ 1 mod 2t. In addition, we bound the metric dimension ol Cartesian products ol circulant graphs.