TY  - JOUR
ID  - Chau2017
LB  - Chau2017
AU  - Chau, Kevin
AU  - Gosselin, Shonda
TI  - The metric dimension of circulant graphs and their Cartesian products
ST  - The metric dimension of circulant graphs and their Cartesian products
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2017
VL  - 37
IS  - 4
SP  - 509
EP  - 534
DO  - http://dx.doi.org/10.7494/OpMath.2017.37.4.509
UR  - http://dx.doi.org/10.7494/OpMath.2017.37.4.509
AB  - 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.
KW  - metric dimension
KW  - circulant graph
KW  - cartesian product
SN  - 1232-9274
ER  -