Sharp lower bounds on the metric dimension of circulant graphs

Knor, Martin; Škrekovski, Riste; Vetrík, Tomáš

doi:10.22049/cco.2023.28792.1725

تعداد نشریات	5
تعداد شماره‌ها	116
تعداد مقالات	1,314
تعداد مشاهده مقاله	1,310,915
تعداد دریافت فایل اصل مقاله	1,217,434

	Sharp lower bounds on the metric dimension of circulant graphs
Communications in Combinatorics and Optimization
مقاله 5، دوره 10، شماره 1، خرداد 2025، صفحه 79-98 اصل مقاله (407.61 K)
نوع مقاله: Original paper
شناسه دیجیتال (DOI): 10.22049/cco.2023.28792.1725
نویسندگان
Martin Knor¹؛ Riste Škrekovski²^{، 3}؛ Tomáš Vetrík^* ⁴
¹Slovak University of Technology, Bratislava, Slovakia
²Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia
³Faculty of Information Studies, Novo Mesto, Slovenia
⁴Department of Mathematics and Applied Mathematics, University of the Free State, Bloemfontein, South Africa
چکیده
For $n \ge 2t+1$ where $t \ge 1$, the circulant graph $C_n (1, 2, \dots , t)$ consists of the vertices $v_0, v_1, v_2, \dots , v_{n-1}$ and the edges $v_i v_{i+1}$, $v_i v_{i+2}, \dots , v_i v_{i + t}$, where $i = 0, 1, 2, \dots , n-1$, and the subscripts are taken modulo $n$. We prove that the metric dimension ${\rm dim} (C_n (1, 2, \dots , t)) \ge \left\lceil \frac{2t}{3} \right\rceil + 1$ for $t \ge 5$, where the equality holds if and only if $t = 5$ and $n = 13$. Thus ${\rm dim} (C_n (1, 2, \dots , t)) \ge \left\lceil \frac{2t}{3} \right\rceil + 2$ for $t \ge 6$. This bound is sharp for every $t \ge 6$.
کلیدواژه‌ها
Cayley graph؛ distance؛ resolving set

مراجع
[1] A. Borchert and S. Gosselin, The metric dimension of circulant graphs and Cayley hypergraphs, Util. Math. 106 (2018), 125–147. [2] K. Chau and S. Gosselin, The metric dimension of circulant graphs and their Cartesian products, Opuscula Math. 37 (2017), no. 4, 509–534. http://doi.org/10.7494/OpMath.2017.37.4.509 [3] R. Gao, Y. Xiao, and Z. Zhang, On the metric dimension of circulant graphs, Canad. Math. Bull. 67 (2024), no. 2, 328–337. https://doi.org/10.4153/S0008439523000759 [4] C. Grigorious, T. Kalinowski, J. Ryan, and S. Stephen, The metric dimension of the circulant graph $C(n, \pm\{1, 2, 3, 4\})$, Australas. J. Combin. 69 (2017), no. 3, 417–441. [5] C. Grigorious, P. Manuel, M. Miller, B. Rajan, and 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 [6] J.T. Hedetniemi, S.T. Hedetniemi, R.C. Laskar, and M. Mulder, The 2-dimension of a tree, Commun. Comb. Optim. 5 (2020), no. 1, 69–81. https://doi.org/10.22049/cco.2019.26495.1119 [7] M. Imran, A.Q. Baig, S.A.U.H. Bokhary, and I. Javaid, On the metric dimension of circulant graphs, Appl. Math. Lett. 25 (2012), no. 3, 320–325. https://doi.org/10.1016/j.aml.2011.09.008 [8] I. Javaid, M.T. Rahim, and K. Ali, Families of regular graphs with constant metric dimension, Util. Math. 75 (2008), 21–33. [9] A. Kelenc, N. Tratnik, and I.G. Yero, Uniquely identifying the edges of a graph: The edge metric dimension, Discrete Appl. Math. 251 (2018), 204–220. https://doi.org/10.1016/j.dam.2018.05.052 [10] T. Vetrík, The metric dimension of circulant graphs, Canad. Math. Bull. 60 (2017), no. 1, 206–216. https://doi.org/10.4153/CMB-2016-048-1 [11] T. Vetrík, On the metric dimension of directed and undirected circulant graphs, Discuss. Math. Graph Theory 40 (2020), no. 1, 67–76. http://doi.org/10.7151/dmgt.2110 [12] T. Vetrík, M. Imran, M. Knor, and R. Škrekovski, The metric dimension of the circulant graph with $2k$ generators can be less than k, J. King Saud Univ. Sci. 35 (2023), no. 7, Article ID: 102834. https://doi.org/10.1016/j.jksus.2023.102834
آمار تعداد مشاهده مقاله: 392 تعداد دریافت فایل اصل مقاله: 1,232

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

آمار

Sharp lower bounds on the metric dimension of circulant graphs