Opuscula Mathematica
Opuscula Math. 45, no. 1 (2025), 39-51

The metric dimension of circulant graphs

Tapendra BC
Shonda Dueck
Abstract. A pair of vertices \(x\) and \(y\) in a graph \(G\) are said to be resolved by a vertex \(w\) if the distance from \(x\) to \(w\) is not equal to the distance from \(y\) to \(w\). We say that \(G\) is resolved by a subset of its vertices \(W\) if every pair of vertices in \(G\) is resolved by some vertex in \(W\). The minimum cardinality of a resolving set for \(G\) is called the metric dimension of \(G\), denoted by \(\dim(G)\). The circulant graph \(C_n(1,2,\ldots,t)\) is the Cayley graph \(Cay(\mathbb{Z}_n:\{\pm 1, \pm 2, \ldots, \pm t\})\). In this note we prove that, for \(n=2kt+2t\), \(\dim(C_n(1,2,\ldots,t))\geq t+2\), confirming Conjecture 4.1.2 in [K. Chau, S. Gosselin, The metric dimension of circulant graphs and their Cartesian products, Opuscula Math. 37 (2017), 509-534].
Keywords: metric dimension, circulant graph.
Mathematics Subject Classification: 05C12, 05C65, 05C25, 05E18.
Full text (pdf)
References ▼
  1. [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. https://doi.org/10.1112/blms/bdq096
  2. [2] A. Borchert, S. Gosselin, The metric dimension of circulant graphs and Cayley hypergraphs, Util. Math. 106 (2018), 125-147.
  3. [3] M. Buratti, Cayley, Marty and Schreier hypergraphs, Abh. Math. Sem. Univ. Hamburg, 64 (1994), 151-162. https://doi.org/10.1007/bf02940782
  4. [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. https://doi.org/10.1137/050641867
  5. [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. https://doi.org/10.1016/s0166-218x(00)00198-0
  6. [6] K. Chau, S. Gosselin, The metric dimension of circulant graphs and their Cartesian products, Opuscula Math. 37 (2017), 509-534. https://doi.org/10.7494/opmath.2017.37.4.509
  7. [7] R. Gao, Y. Xiao, Z. Zhang, On the metric dimension of circulant graphs, Canad. Math. Bull. 67 (2023), 328-337. https://doi.org/10.4153/s0008439523000759
  8. [8] 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. https://doi.org/10.1016/j.amc.2014.09.045
  9. [9] F. Harary, R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191-195.
  10. [10] 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. https://doi.org/10.1016/j.aml.2011.09.008
  11. [11] I. Javaid, M.T. Rahim, K. Ali, Families of regular graphs with constant metric dimension, Util. Math. 75 (2008), 21-33.
  12. [12] S. Khuller, B. Raghavachari, A. Rosenfeld, Localization in graphs, Technical Report (1994).
  13. [13] J. Peters-Fransen, O.R. Oellermann, The metric dimension of Cartesian products of graphs, Util. Math. 69 (2006), 33-41.
  14. [14] S.C. Shee, On group hypergraphs, Southeast Asian Bull. Math. 14 (1990), 49-57.
  15. [15] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549-559.
  16. [16] P.J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22 (1988), 445-455.
  17. [17] T. Vetrík, The metric dimension of circulant graphs, Canad. Math. Bull. 60 (2017), 206-216. https://doi.org/10.4153/cmb-2016-048-1
  18. [18] T. Vetrík, M. Imran, M. Knor, R. Škrekovski, The metric dimension of the circulant graph with \(2t\) generators can be less than \(t\), J. King Saud. Univ. Sci. 35 (2023), 102834. https://doi.org/10.1016/j.jksus.2023.102834
About the authors ▼
Tapendra BC
Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Avenue, Winnipeg, Manitoba, R3B 2E9, Canada
Shonda Dueck (corresponding author)
Department of Mathematics and Statistics, University of Winnipeg, 515 Portage Avenue, Winnipeg, Manitoba, R3B 2E9, Canada
About the article ▼
Communicated by Adam Paweł Wojda.
Received: 2023-11-21.
Revised: 2024-08-16.
Accepted: 2024-10-15.
Published online: 2024-12-20.
Cite this article as ▼
Tapendra BC, Shonda Dueck, The metric dimension of circulant graphs, Opuscula Math. 45, no. 1 (2025), 39-51, https://doi.org/10.7494/OpMath.2025.45.1.39.
Download this article's citation as: