Opuscula Math. 45, no. 1 (2025), 39-51
https://doi.org/10.7494/OpMath.2025.45.1.39
Opuscula Mathematica
The metric dimension of circulant graphs
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.
- 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
- A. Borchert, S. Gosselin, The metric dimension of circulant graphs and Cayley hypergraphs, Util. Math. 106 (2018), 125-147.
- M. Buratti, Cayley, Marty and Schreier hypergraphs, Abh. Math. Sem. Univ. Hamburg, 64 (1994), 151-162. https://doi.org/10.1007/bf02940782
- 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
- 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
- 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
- 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
- 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
- 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. https://doi.org/10.1016/j.aml.2011.09.008
- 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. 60 (2017), 206-216. https://doi.org/10.4153/cmb-2016-048-1
- 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
- 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
- Communicated by Adam Paweł Wojda.
- Received: 2023-11-21.
- Revised: 2024-08-16.
- Accepted: 2024-10-15.
- Published online: 2024-12-20.
