The Metric Dimension of Circulant Graphs
Tomáš Vetrík · Canadian Mathematical Bulletin · 2016
Abstract. A subsetWof the vertex set of a graphGis called aresolving setofGif for every pair of distinct verticesu,vofG, there isw∊Wsuch that the distance ofwanduis different from the distance ofwandv. The cardinality of a smallest resolving set is called the metric dimension ofG, denoted by dim(G). The circulant graphCn(1, 2, . . . ,t) consists of the verticesv0,v1, . . . ,vn−1and the edgesvivi+j, where 0 ≤i≤n− 1, 1 ≤j≤t( ), the indices are taken modulon. Grigorious, Manuel, Miller, Rajan, and Stephen proved that dim(Cn(1, 2, . . . ,t)) ≥t+ 1 for , and they presented a conjecture saying that dim(Cn(1, 2, . . . ,t)) =t+p− 1 forn= 2tk+t+p, where 3 ≤p≤t+ 1. We disprove both statements. We show that ift≥ 4 is even, there exists an infinite set of values ofnsuch that dim(Cn(1, 2, . . . ,t)) =t. We also prove that dim(Cn(1, 2, . . . ,t)) ≤t+p/2 forn= 2tk+t+p, wheretandpare even,t≥ 4, 2 ≤p≤t, andk≥ 1.