The metric dimension of the circulant graph with 2k generators can be less than k

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

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

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

Original languageEnglish
Article number102834
JournalJournal of King Saud University - Science
Volume35
Issue number7
DOIs
Publication statusPublished - Oct 2023

Keywords

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

ASJC Scopus subject areas

  • General

Fingerprint

Dive into the research topics of 'The metric dimension of the circulant graph with 2k generators can be less than k'. Together they form a unique fingerprint.

Cite this