On the metric dimension of circulant graphs

Let G=(V,E)G=(V,E) be a connected graph and d(x,y)d(x,y) be the distance between the vertices xx and yyinV(G)V(G). A subset of vertices W={w1,w2,…,wk}W={w1,w2,…,wk} is called a resolving set or locating set for GG if for every two distinct vertices x,y∈V(G)x,y∈V(G), there is a vertex wi∈Wwi∈W such that d(x,wi)≠d(y,wi)d(x,wi)≠d(y,wi)fori=1,2,…,ki=1,2,…,k. A resolving set containing the minimum number of vertices is called a metric basis   for GG and the number of vertices in a metric basis is its metric dimension  , denoted by dim(G)dim(G).Let FF be a family of connected graphs Gn:F=(Gn)n≥1Gn:F=(Gn)n≥1 depending on nn as follows: the order |V(G)|=φ(n)|V(G)|=φ(n) and limn→∞φ(n)=∞limn→∞φ(n)=∞. If there exists a constant C>0C>0 such that dim(Gn)≤Cdim(Gn)≤C for every n≥1n≥1 then we shall say that FF has bounded metric dimension.The metric dimension of a class of circulant graphs Cn(1,2)Cn(1,2) has been determined by Javaid and Rahim (2008) [13]. In this paper, we extend this study to an infinite class of circulant graphs Cn(1,2,3)Cn(1,2,3). We prove that the circulant graphs Cn(1,2,3)Cn(1,2,3) have metric dimension equal to 4 for n≡2,3,4,5(mod6). For n≡0(mod6) only 5 vertices appropriately chosen suffice to resolve all the vertices of Cn(1,2,3)Cn(1,2,3), thus implying that dim(Cn(1,2,3))≤5dim(Cn(1,2,3))≤5 except n≡1(mod6) when dim(Cn(1,2,3))≤6dim(Cn(1,2,3))≤6.