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_{i}v_{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 $2$t. 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.