Opuscula Math. 37, no. 4 (2017), 509-534

http://dx.doi.org/10.7494/OpMath.2017.37.4.509

http://dx.doi.org/10.7494/OpMath.2017.37.4.509

Opuscula Mathematica

Kevin Chau

Shonda Gosselin

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.

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)

orexport to RefWorks .

Kevin Chau, Shonda Gosselin, The metric dimension of circulant graphs and their Cartesian products, Opuscula Math. 37, no. 4 (2017), 509-534,

Download this article's citation as:

or

ISSN 1232−9274, e-ISSN 2300−6919, DOI http://dx.doi.org/10.7494/OpMath

Copyright © 2003−2017 OPUSCULA MATHEMATICA

Contact: opuscula@agh.edu.pl

Made by Tomasz Zabawa