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

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.

- R.F. Bailey, P.J. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bull. London Math. Soc. 43 (2011), 209-242.
- A. Borchert, S. Gosselin, The metric dimension of circulant graphs and Cayley hypergraphs, (2015), to appear.
- M. Buratti, Cayley, Marty and Schreier hypergraphs, Abh. Math. Sem. Univ. Hamburg 64 (1994), 151-162.
- J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas, C. Seara, D.R. Wood, On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math. 21 (2007), 423-441.
- G. Chartrand, L. Eroh, M. Johnson, O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000), 99-113.
- C. Grigorious, P. Manuel, M. Miller, B. Rajan, S. Stephen, On the metric dimension of circulant and Harary graphs, Appl. Math. Comput. 248 (2014), 47-54.
- F. Harary, R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191-195.
- M. Imran, A.Q. Baig, S.A.U.H. Bokhary, I. Javaid, On the metric dimension of circulant graphs, Appl. Math. Let. 25 (2012), 320-325.
- I. Javaid, M.T. Rahim, K. Ali, Families of regular graphs with constant metric dimension, Util. Math. 75 (2008), 21-33.
- S. Khuller, B. Raghavachari, A. Rosenfeld, Localization in graphs, Technical Report (1994).
- J. Peters-Fransen, O.R. Oellermann, The metric dimension of Cartesian products of graphs, Util. Math. 69 (2006), 33-41.
- S.C. Shee, On group hypergraphs, Southeast Asian Bull. Math. 14 (1990), 49-57.
- P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549-559.
- P.J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22 (1988), 445-455.
- T. Vetrík, The metric dimension of circulant graphs, Canad. Math. Bull. (2016), to appear.

- Kevin Chau
- University of Winnipeg, Department of Mathematics and Statistics, 515 Portage Avenue, Winnipeg, Manitoba, R3B 2E9, Canada

- Shonda Gosselin
- University of Winnipeg, Department of Mathematics and Statistics, 515 Portage Avenue, Winnipeg, Manitoba, R3B 2E9, Canada

- Communicated by Mirko Horňák.

- Received: 2016-08-29.
- Revised: 2017-02-09.
- Accepted: 2017-02-13.
- Published online: 2017-04-28.