The metric dimension of circulant graphs and their Cartesian products

Abstract

Let \(G=(V,E)\) be a connected graph (or hypergraph) and let \(d(x,y)\) denote the distance between vertices \(x,y\in V(G)\). A subset \(W\subseteq V(G)\) is called a resolving set for \(G\) if for every pair of distinct vertices \(x,y\in V(G)\), there is \(w\in W\) such that \(d(x,w)\neq d(y,w)\). The minimum cardinality of a resolving set for \(G\) is called the metric dimension of \(G\), denoted by \(\beta(G)\). The circulant graph \(C_n(1,2,\ldots,t)\) has vertex set \(\{v_0,v_1,\ldots,v_{n-1}\}\) and edges \(v_iv_{i+j}\) where \(0\leq i\leq n-1\) and \(1\leq j\leq t\) and the indices are taken modulo \(n\) (\(2\leq t\leq\left\lfloor\frac{n}{2}\right\rfloor\)). In this paper we determine the exact metric dimension of the circulant graphs \(C_n(1,2,\ldots,t)\), extending previous results due to Borchert and Gosselin (2013), Grigorious et al. (2014), and Vetrík (2016). In particular, we show that \(\beta(C_n(1,2,\ldots,t))=\beta(C_{n+2t}(1,2,\ldots,t))\) for large enough \(n\), which implies that the metric dimension of these circulants is completely determined by the congruence class of \(n\) modulo \(2t\). We determine the exact value of \(\beta(C_n(1,2,\ldots,t))\) for \(n\equiv 2\bmod 2t\) and \(n\equiv (t+1)\bmod 2t\) and we give better bounds on the metric dimension of these circulants for \(n\equiv 0\bmod 2t\) and \(n\equiv 1 \bmod 2t\). In addition, we bound the metric dimension of Cartesian products of circulant graphs.

Keywords

• metric dimension
• circulant graph
• cartesian product