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)

1. 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.
2. A. Borchert, S. Gosselin, The metric dimension of circulant graphs and Cayley hypergraphs, (2015), to appear.
3. M. Buratti, Cayley, Marty and Schreier hypergraphs, Abh. Math. Sem. Univ. Hamburg 64 (1994), 151-162.
4. 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.
5. 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.
6. 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.
7. F. Harary, R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191-195.
8. 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.
9. I. Javaid, M.T. Rahim, K. Ali, Families of regular graphs with constant metric dimension, Util. Math. 75 (2008), 21-33.
10. S. Khuller, B. Raghavachari, A. Rosenfeld, Localization in graphs, Technical Report (1994).
11. J. Peters-Fransen, O.R. Oellermann, The metric dimension of Cartesian products of graphs, Util. Math. 69 (2006), 33-41.
12. S.C. Shee, On group hypergraphs, Southeast Asian Bull. Math. 14 (1990), 49-57.
13. P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549-559.
14. P.J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22 (1988), 445-455.
15. 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.
• Revised: 2017-02-09.
• Accepted: 2017-02-13.
• Published online: 2017-04-28.