Sharp lower bounds on the metric dimension of circulant graphs

Knor, Martin; Skrekovski, Riste; Vetrik, Tomas

doi:10.22049/cco.2023.28792.1725

تعداد نشریات	7
تعداد شماره‌ها	102
تعداد مقالات	1,145
تعداد مشاهده مقاله	1,053,628
تعداد دریافت فایل اصل مقاله	875,993

	Sharp lower bounds on the metric dimension of circulant graphs
Communications in Combinatorics and Optimization
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 07 دی 1402 اصل مقاله (408.1 K)
نوع مقاله: Original paper
شناسه دیجیتال (DOI): 10.22049/cco.2023.28792.1725
نویسندگان
Martin Knor¹؛ Riste Skrekovski²؛ Tomas Vetrik^* ³
¹Slovak University of Technology, Bratislava, Slovakia
²Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia
³University of the Free State
چکیده
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. (In press) 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
آمار تعداد مشاهده مقاله: 142 تعداد دریافت فایل اصل مقاله: 366

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

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

آمار

Sharp lower bounds on the metric dimension of circulant graphs