Opuscula Mathematica
Opuscula Math. 37, no. 4 (), 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



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.
Cite this article as:
Kevin Chau, Shonda Gosselin, The metric dimension of circulant graphs and their Cartesian products, Opuscula Math. 37, no. 4 (2017), 509-534, http://dx.doi.org/10.7494/OpMath.2017.37.4.509
 
Download this article's citation as:
a .bib file (BibTeX), a .ris file (RefMan), a .enw file (EndNote)
or export to RefWorks.

RSS Feed

horizontal rule

ISSN 1232−9274, e-ISSN 2300−6919, DOI https://doi.org/10.7494/OpMath
Copyright © 2003−2017 OPUSCULA MATHEMATICA
Contact: opuscula@agh.edu.pl
Made by Tomasz Zabawa

horizontal rule

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.