The metric dimension of circulant graphs

• Autorzy: BC, Tapendra , Dueck, Shonda
• 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

• 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.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025)

Identyfikatory

DOI

10.7494/OpMath.2025.45.1.39