TY - JOUR
T1 - The metric dimension of the circulant graph with 2k generators can be less than k
AU - Vetrík, Tomáš
AU - Imran, Muhammad
AU - Knor, Martin
AU - Škrekovski, Riste
N1 - Publisher Copyright:
© 2023 The Author(s)
PY - 2023/10
Y1 - 2023/10
N2 - Circulant graphs are useful networks because of their symmetries. For k⩾2 and n⩾2k+1, the circulant graph Cn(1,2,…,k) consists of the vertices v0,v1,v2,…,vn-1 and the edges vivi+1,vivi+2,…,vivi+k, where i=0,1,2,…,n-1, and the subscripts are taken modulo n. The metric dimension β(Cn(1,2,…,k)) of the circulant graphs Cn(1,2,…,k) for general k (and n) has been studied in several papers. In 2017, Chau and Gosselin proved that β(Cn(1,2,…,k))⩾k for every k, and they conjectured that if n=2k+r, where k is even and 3⩽r⩽k-1, then β(Cn(1,2,…,k))=k. We disprove both by showing that for every k⩾9, there exists an n∈[2k+5,2k+8]⊂[2k+3,3k-1] such that [Formula presented]. We conjecture that for k⩾6,β(Cn(1,2,…,k)) cannot be less than [Formula presented].
AB - Circulant graphs are useful networks because of their symmetries. For k⩾2 and n⩾2k+1, the circulant graph Cn(1,2,…,k) consists of the vertices v0,v1,v2,…,vn-1 and the edges vivi+1,vivi+2,…,vivi+k, where i=0,1,2,…,n-1, and the subscripts are taken modulo n. The metric dimension β(Cn(1,2,…,k)) of the circulant graphs Cn(1,2,…,k) for general k (and n) has been studied in several papers. In 2017, Chau and Gosselin proved that β(Cn(1,2,…,k))⩾k for every k, and they conjectured that if n=2k+r, where k is even and 3⩽r⩽k-1, then β(Cn(1,2,…,k))=k. We disprove both by showing that for every k⩾9, there exists an n∈[2k+5,2k+8]⊂[2k+3,3k-1] such that [Formula presented]. We conjecture that for k⩾6,β(Cn(1,2,…,k)) cannot be less than [Formula presented].
KW - Cayley graph
KW - Circulant graph
KW - Distance
KW - Metric dimension
KW - Resolving set
UR - http://www.scopus.com/inward/record.url?scp=85168569201&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85168569201&partnerID=8YFLogxK
U2 - 10.1016/j.jksus.2023.102834
DO - 10.1016/j.jksus.2023.102834
M3 - Article
AN - SCOPUS:85168569201
SN - 1018-3647
VL - 35
JO - Journal of King Saud University - Science
JF - Journal of King Saud University - Science
IS - 7
M1 - 102834
ER -