## Abstract

Circulant graphs are useful networks because of their symmetries. For k⩾2 and n⩾2k+1, the circulant graph C_{n}(1,2,…,k) consists of the vertices v_{0},v_{1},v_{2},…,v_{n-1} and the edges v_{i}v_{i+1},v_{i}v_{i+2},…,v_{i}v_{i+k}, where i=0,1,2,…,n-1, and the subscripts are taken modulo n. The metric dimension β(C_{n}(1,2,…,k)) of the circulant graphs C_{n}(1,2,…,k) for general k (and n) has been studied in several papers. In 2017, Chau and Gosselin proved that β(C_{n}(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 β(C_{n}(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,β(C_{n}(1,2,…,k)) cannot be less than [Formula presented].

Original language | English |
---|---|

Article number | 102834 |

Journal | Journal of King Saud University - Science |

Volume | 35 |

Issue number | 7 |

DOIs | |

Publication status | Published - Oct 2023 |

## Keywords

- Cayley graph
- Circulant graph
- Distance
- Metric dimension
- Resolving set

## ASJC Scopus subject areas

- General