The metric dimension of circulant graphs

• Autorzy: BC Tapendra , Dueck Shonda

Identyfikatory

DOI

10.7494/OpMath.2025.45.1.39

• Języki publikacji: EN

Abstrakty

EN

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 Cn(1, 2, . . . , t) is the Cayley graph Cay(Zn : {±1,±2, . . . ,±t}). In this note we prove that, for n = 2kt + 2t, dim(Cn(1, 2, . . . , t)) ≥ 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].

Słowa kluczowe

EN

metric dimension; circulant graph

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2025
• Tom: Vol. 45, no. 1
• Strony: 39--51
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

BC Tapendra

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

autor

Dueck Shonda

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

Bibliografia

• [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, Util. Math. 106 (2018), 125–147.
• [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] K. Chau, S. Gosselin, The metric dimension of circulant graphs and their Cartesian products, Opuscula Math. 37 (2017), 509–534.
• [7] R. Gao, Y. Xiao, Z. Zhang, On the metric dimension of circulant graphs, Canad. Math. Bull. 67 (2023), 328–337.
• [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.
• [9] F. Harary, R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191–195.
• [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.
• [11] I. Javaid, M.T. Rahim, K. Ali, Families of regular graphs with constant metric dimension, Util. Math. 75 (2008), 21–33.
• [12] S. Khuller, B. Raghavachari, A. Rosenfeld, Localization in graphs, Technical Report (1994).
• [13] J. Peters-Fransen, O.R. Oellermann, The metric dimension of Cartesian products of graphs, Util. Math. 69 (2006), 33–41.
• [14] S.C. Shee, On group hypergraphs, Southeast Asian Bull. Math. 14 (1990), 49–57.
• [15] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549–559.
• [16] P.J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22 (1988), 445–455.
• [17] T. Vetrík, The metric dimension of circulant graphs, Canad. Math. Bull. 60 (2017), 206–216.
• [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.