Opuscula Math. 37, no. 4 (2017), 509-534
http://dx.doi.org/10.7494/OpMath.2017.37.4.509

Opuscula Mathematica

# The metric dimension of circulant graphs and their Cartesian products

Kevin Chau
Shonda Gosselin

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.

Mathematics Subject Classification: 05C12, 05C65, 05C25, 05E18.

Full text (pdf)