Sharp lower bounds on the metric dimension of circulant graphs

Document Type : Original paper

Authors

1 Slovak University of Technology, Bratislava, Slovakia

2 Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia

3 University of the Free State

Abstract

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

Keywords

Main Subjects

References

[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
 
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 28 December 2023

Files

Share

How to cite

Statistics