# Resolvability in Subdivision of Circulant NetworksCn1,k

Authors: Jianxin Wei; Syed Ahtsham Ul Haq Bokhary; Ghulam Abbas; Muhammad Imran
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

Circulant networks form a very important and widely explored class of graphs due to their interesting and wide-range applications in networking, facility location problems, and their symmetric properties. A resolving set is a subset of vertices of a connected graph such that each vertex of the graph is determined uniquely by its distances to that set. A resolving set of the graph that has the minimum cardinality is called the basis of the graph, and the number of elements in the basis is called the metric dimension of the graph. In this paper, the metric dimension is computed for the graphGn1,k constructed from the circulant graph Cn1,k by subdividing its edges. We have shown that, for k=2, Gn1,k has an unbounded metric dimension, and for k=3 and 4, Gn1,k has a bounded metric dimension.


---

## Body

## 1. Introduction

Resolvability of graphs becomes an important parameter in graph theory due to its wide applications in different branches of mathematics, such as facility location problems, chemistry, especially molecular chemistry [1], the method of positioning robot networks [2], the optimization problem in combinatorics [3], applications in pattern recognition and image processing [4], and the problems of sonar and Coast Guard LORAN [5].The resolvability of graphs depends on the distances in graphs. The distance between two vertices in a connected graph is the smallest distance connecting those two vertices. The representation of a vertexu with respect to the set W is denoted by ru,W and is defined as a k-tupple (d(u,w1), \dots, d(u,wn)), where w1, \dots, wn \in W. The set W is called the resolving set [1] or sometimes locating set [5] if each vertex of the graph has a unique representation with respect to W. A resolving set of the graph that has the minimum cardinality is called the basis of the graph, and the number of elements in the basis is called the metric dimension of the graph, generally denoted by βG.Motivated by the problem of uniquely determining the location of an intruder in a network, the concept of metric dimension was first introduced by Slater in [5, 6] and studied independently by Harary and Melter in [7]. Applications of this invariant to the navigation of robots in networks are discussed in [2], and applications to chemistry are given in [1], while applications to the problem of pattern recognition and image processing, some of which involve the use of hierarchical data structures, are given in [4].A family of connected graphsF is said to have a bounded metric dimension if the metric dimension of each graph in F is bounded above by a positive integer. Otherwise, F has an unbounded metric dimension.If every graphF has a constant metric dimension, then F is said to have constant metric dimension. A connected graph G has βG=1 if and only if G is the path [1]; cycles Cn have metric dimension 2 for every n≥3. Also, generalized Peterson graphs Pn,2, antiprism An, and circulant graphs Cn1,2 are families of graphs with constant metric dimension. The families of graphs having constant metric dimension are studied in [8–23].It is important to note that to determine the graph has a bounded metric dimension is an NP-complete problem [19]. Some bounds for this parameter, in terms of the diameters of the graph, are given in [2], and it was shown in [1, 2, 4, 20] that the metric dimension of the tree can be determined efficiently. However, it is highly unlikely to determine the dimension of the graph unless the graph belongs to such family for which the distance between vertices can be computed systematically.Geometrically, by subdividing an edge, we mean to insert a new vertex in the edge such that the existing edge is divided into two edges. The subdivision of the graphG is a graph obtained after performing a sequence of edge subdivision. Subdivision of graphs is an important tool to determine whether the graph is planar or not. In [24], plane graphs are characterized using subdivision as follows:A necessary and sufficient condition of a graph to be planar is that each of its subdivision is planarA necessary and sufficient condition of a graph to be planar is if it does not contain a subdivision ofK5 or K3,3In this paper, we have investigated the resolvability of subdivision of circulant graphCn1,k for k≥2. It is shown that, for k=2, this class has an unbounded metric dimension, and for k=3 and 4, it has a bounded metric dimension.


## 2. Metric Dimension of Subdivision of Circulant GraphCn1,k for k≥2

The circulant graphs are an important class of graphs that can be used in local area networks.A circulant graph onn vertices and m parameters a1,…,am, where each parameter ai is at most half of n, is denoted by Cna1,a2,...,am. If v1,…,vn are vertices of Cna1,a2,...,am, then there is an edge between two vertices vi and vj if and only if i−j is one of ai. The parameters of ai are called generators of Cna1,a2,…,am.The graphGna1,…,ak is a graph obtained from Cna1,a2,...,am by subdividing all the edges of Cna1,a2,...,am except the edges between vertices vi and vi+1.In this paper, the resolvability ofGn1,k is investigated. Let ui be the added vertex in each of the edge vivi+k. Thus, the graph Gn1,k has 2n vertices and 3n edges. Let xi and xj be two vertices of Gn1,k; then, the gap between vertices xi and xj is defined to be i−j, where 1≤i<j≤n.In the following theorem, it is shown that the metric dimension of the graphGn1,2 is unbounded.Theorem 1.
Forn≥9,(1)βGn1,2=n3.Proof.
LetW=xi:1≤i≤q be a minimum resolving set of Gn1,2. We have two cases: either xi=vi or xi=ui, for some i□.Claim 1.
Ifxi=vi for some i, then vi+2 also belongs to W because, otherwise, vi+2 and ui+1 will have the same representation.Claim 2.
Ifxi=ui for some i, then ui+3 must belong to W because, otherwise, vi+3 and ui+2 will have the same representation.
Both these case imply that the two consecutive vertices inW can have at most distance 3. Thus, the gap between two vertices of W is at most 3. Since vertices presented on the outer cycle are n, therefore, q≥n/3. Hence,(2)βGn1,2≥n3.
To prove the upper bound, consider the setW=u3i−2:i=1,2,…,n/3 of vertices of Gn1,2. The construction of W shows that every vertex in W determines a gap of size 3.
For1≤i≤n/3, let S=vi,vi+1,vi+2,vi+3,ui+1,ui+2 be the set of vertices determined by the two consecutive vertices ui and ui+3. It is enough to show that every vertex in S is uniquely determined by some vertices in W.The verticesvi and vi+2 are the only vertices in Gn1,2 that are at distance 1 from ui, but dvi,ui+3=4 and dvi+2,ui+3=2.The verticesvi−1, vi+1, vi+3, ui+2, and ui−2 are the only vertices in Gn1,2 that are at distance 2 from ui. The vertices vi−1 and ui−2 also have the same distance 5 from ui+3, but they can be resolved by the vertex u4n/3−1. The vertices vi+1 and ui+2 also have the same distance 3 from ui+3, but they can be resolved by the vertex ui+6. The vertex vi+3 is the unique vertex in Gn1,2 such that dvi+3,ui+3=1 and dvi+3,ui=2.The vertexui+1 is the unique vertex in Gn1,2 such that dui+1,ui+3=2 and dui+1,ui=3.
This shows that every vertex in the setS is uniquely determined by some vertices in the set W. Thus, W becomes a resolving set, and(3)βGn1,2≤n3.
From equations (2) and (3), we have βGn1,2=n/3.
In the next results, it is shown that the graphGn1,k has constant metric dimension for 3≤k≤4.Theorem 2.
Forn≥14,ifn=2rmmod3,then,(4)βGn1,3=3.Proof.
LetW=u1,u3,u5 be the set of vertices in Gn1,3. It is enough to show that every vertex of the graph Gn1,3 is determined uniquely by some of the vertices in W. For this, the representations of each vertex are calculated as follows.
The verticesv1,…,v7 have representations 1,3,4, 2,2,3, 2,1,3, 1,2,2, 2,2,1, 3,1,2, 3,2,2, respectively.
The representations of the remaining verticesvi:7≤i≤n of Gn1,3 are calculated as follows:(5)rvi,W=2i−53,2i−93,2i−133,for8≤i≤n2+2,2n+23−2i−53,2i−93,2i−133,fori=n2+3,2n+23−2i−53,2n+113−2i3,2i−133,fori=n2+4,2n+23−2i−53,2n+113−2i3,2n+23−2i−93,fori=n2+5,2n+23−2i−53,2n+23−2i−93,2n+23−2i−93,forn2+6≤i≤n.
The verticesu2,u4,u6,u7,un−1,un of Gn1,3 have representations 3,3,2, 2,3,3, 4,2,3, 4,3,3, 3,3,4, 3,2,4, respectively.
For the remaining vertices, we have(6)rui,W=2i−23,2i−63,2i−103,for8≤i≤n2+1,2n−13−2i−53,2i−83,2i−113,fori=n2+2,2n−13−2i−53,2n+83−2i3,2i−103,fori=n2+3,2n−13−2i−53,2n+83−2i3,2n+23−2i−63,fori=n2+4,2n+23−2i−23,2n+23−2i−63,2n+23−2i−103,forn2+5≤i≤n−2.
This shows that every vertex of the graphGn1,3 is determined uniquely by some of the vertices in W. Hence, W becomes a resolving set, and(7)βGn1,3≤3.
Now, to compute the lower bound, suppose, on contrary, thatW is a minimum resolving set of Gn1,3 of cardinality 2. We have the following possibilities to choose the vertices of W.□


### 2.1. IfW Contains Both Vertices from vi

One can suppose without losing any generality thatW=v1,vj:2≤j≤n. However, in this case, if j≡2mod3, then(8)ruj,W=rvj+1,W=2j3,1,for2≤j≤n2,2n−2j3,1,forn2+1≤j≤n,and if j≡0,1mod3, then(9)ruj+1,W=rvj+2,W=2j+23,2,for2≤j≤n2,2n−2j−23,2forn2+1≤j≤n.


### 2.2. IfW Contains Both Vertices from ui

One can suppose without losing any generality thatW=u1,uj:2≤j≤n. However, in this case, if j≡0mod3, then(10)ruj+1,W=rvj+2,W=2j3,3,for2≤j≤n2,2n−2j3,3,forn2+1≤j≤n,and if j≡1,2mod3,(11)ruj+3,W=rvj+4,W=2j+33,2,for2≤j≤n2,2n−2j−33,2,forn2+1≤j≤n.


### 2.3. If One Each fromvi and uj Belongs to W

One can suppose without losing any generality thatW=vi,uj:1≤i≤j≤n. However, in this case, if j≡0mod3, then(12)ruj+4,W=rvj+5,W=2j3+3,3,for3≤j≤n2−2,2n−2j−83,3,forn2−1≤j≤n,and if j≡1,2mod3,(13)ruj+3,W=rvj+4,W=2j3+2,2,for1≤j≤n2,2n−2j−63,2,forn2+1≤j≤n.Thus, there is no resolving set ofGn1,3 having two vertices. This implies that(14)βGn1,3≥3.From (7) and (14), we get(15)βGn1,3=3.Theorem 3.
Forn≥15, if n≡0,1mod3, then(16)βGn1,3=4.Proof.
LetW=v1,v2,v3,v4 be the set of vertices in Gn1,4. It is enough to show that every vertex of the graph Gn1,4 is uniquely determined by some vertices in W. For this, the representations of each vertex are calculated as follows.
The representations of outer verticesvi:1≤i≤n of Gn1,3 are calculated as follows:(17)rvi,W=2i−23,2i−43,2i−63,2i−83,for5≤i≤n+12,2n−2i+23,2n−2i+43,2n−2i+63,2n−2i+83,forn+12+4≤i≤n.
Ifi=n+1/2+1,(18)rvi,W=2i−63,2i−63,2i−63,2i−83,forn=6kandk≥3,2i−43,2i−43,2i−43,2i−73,forn=6k+1andk≥3,2i−43,2i−43,2i−63,2i−63,forn=6k+3andk≥2,2i−53,2i−33,2i−53,2i−83,forn=6k+4andk≥2.
Ifi=n+1/2+2,(19)rvi,W=2i−103,2i−83,2i−83,2i−83,forn=6kandk≥3,2i−63,2i−63,2i−63,2i−63,forn=6k+1andk≥3,2i−83,2i−63,2i−63,2i−83,forn=6k+3andk≥2,2i−103,2i−73,2i−43,2i−73forn=6k+4andk≥2.
Ifi=n+1/2+3,(20)rvi,W=2i−143,2i−123,2i−103,2i−103,forn=6kandk≥3,2i−113,2i−83,2i−83,2i−83,forn=6k+1andk≥3,2i−103,2i−103,2i−83,2i−83,forn=6k+3andk≥2,2i−123,2i−123,2i−93,2i−63,forn=6k+4andk≥2.
The verticesu1,u2,u3,u4,un−1,un have representations 1,2,2,1, 2,1,2,2, 3,2,1,2, 3,3,2,1, 2,1,2,3, 2,2,1,2, respectively.
The representations of the remaining verticesui of Gn1,3 are calculated as follows:(21)rui,W=2i+13,2i−13,2i−33,2i−53,for5≤i≤n2−1,2n−2i−13,2n−2i+13,2n−2i+33,2n−2i+53,forn2+3≤i≤n−2.
Ifi=n/2,(22)rui,W=2i−13,2i−13,2i−33,2i−33,forn=6kandk≥3,2i−23,2i+13,2i−23,2i−53,forn=6k+1andk≥3,2i−13,2i−13,2i−13,2i−43,forn=6k+3andk≥2,2i−13,2i−13,2i−13,2i−43,forn=6k+4andk≥2.
Ifi=n/2+1,(23)rui,W=2i−63,2i−43,2i−43,2i−63,forn=6kandk≥3,2i−73,2i−43,2i−13,2i−43,forn=6k+1andk≥3,2i−63,2i−43,2i−43,2i−43,forn=6k+3andk≥2,2i−33,2i−33,2i−33,2i−33,forn=6k+4andk≥2.
Ifi=n/2+2,(24)rui,W=2i−73,2i−73,2i−53,2i−53,forn=6kandk≥3,2i−93,2i−93,2i−63,2i−33,forn=6k+1andk≥3,2i−113,2i−93,2i−73,2i−73,forn=6k+3andk≥2,2i−83,2i−53,2i−53,2i−53,forn=6k+4andk≥2.
This shows that every vertex of the graphGn1,4 is uniquely determined by some of the vertices in W. Hence, W become a resolving set, and(25)βGn1,4≤4.
Letn=6k+l and l∈0,1,3,4. We show that there is no resolving set of Gn1,4 with three elements. Suppose, on contrary, that W is a minimum resolving set of Gn1,4 of cardinality 3. We have the following possibilities to choose the vertices of W.□


### 2.4. If Onlyvi∈W

One can suppose without losing any generality thatW=v1,vi,vj, where 2≤i≤3k and i+1≤j≤6k. In this case, the vertices of Gn1,4 that have the same representation for all choices of the resolving set are given as follows:(26)run−3=rvn−1=2,2i+33,2j+43,fori≡0mod3,j≡0,1mod3and for every value ofl,run+3/2=rvn+5/2=n−33,n−i+13,n−2j+53,forl=1,3andi≡0mod3,j≡2mod3,run/2=rvn+2/2=n3,n−i+13,n−2j+33,for1l=0,4andi≡0mod3,j≡2mod3,run−2=rvn=1,2i3,2j+13,otherwise and for alll.


### 2.5. If Two Vertices fromvi and One Vertex from uj Belong to W

One can suppose without losing any generality thatW=v1,vi,uj, where 2≤i≤3k and i≤j≤6k.In this case, the vertices ofGn1,4 that have the same representation for all choices of the resolving set are given as follows:(27)run−3=rvn−1=2,2i+33,2j+43,fori≡0mod3,j≡0,1mod3and for alll,run+3/2=rvn+5/2=n−33,n−i+13,n−2j+53,forl=1,3andi≡0mod3,j≡2mod3,run/2=rvn+2/2=n3,n−i+13,n−2j+33,forl=0,4andi≡0mod3,j≡2mod3,run−2=rvn=1,2i3,2j+13,otherwise and for alll.


### 2.6. If Two Vertices fromui and One Vertex from vj Belong to W

One can suppose without losing any generality thatW=v1,ui,uj, where 1≤i≤3k and i≤j≤6k.In this case, the vertices ofGn1,4 that have the same representation for all choices of the resolving set are given as follows:(28)run−3=rvn−1=2,2i+33,2j+43,fori≡0mod3,j≡0,1mod3and for alll,run+3/2=rvn+5/2=n−33,n−i+13,n−2j+53,forl=1,3andi≡0mod3,j≡2mod3,run/2=rvn+2/2=n3,n−i+13,n−2j+33,forl=0,4andi≡0mod3,j≡2mod3and forl=,run−2=rvn=1,2i3,2j+13,otherwise and for alll.


### 2.7. IfW Contains All Three Vertices from ui

One can suppose without losing any generality thatW=u1,ui,uj is a resolving set, where 2≤i≤3k and i+1≤j≤6k.In this case, the vertices ofGn1,4 that have the same representation for all choices of the resolving set are given as follows:(29)run−3=rvn−1=2,2i+33,2j+43,fori≡0mod3,j≡0,1mod3and for alll,run+3/2=rvn+5/2=n−33,n−i+13,n−2j+53,forl=1,3andi≡0mod3,j≡2mod3,run/2=rvn+2/2=n3,n−i+13,n−2j+33,forl=0,4andi≡0mod3,j≡2mod3,run−2=rvn=1,2i3,2j+13,otherwise and for alll.Thus, there is no resolving set ofGn1,4 having three elements. Hence,(30)βGn1,4≥4.From equations (25) and (30), we get(31)βGn1,4=4.Theorem 4.
Forn≥20, if n≡3mod4, then(32)βGn1,4=4.Proof.
LetW=u1,u4,u7,u10 be the set of vertices in Gn1,4. It is enough to show that every vertex of the graph Gn1,4 is uniquely determined by some vertices in W. For this, the vertices v1,…,v11 have representations 1,4,5,6, 2,3,4,5, 3,2,3,6, 2,1,4,5, 1,2,3,4, 2,3,2,3, 3,2,1,4, 4,1,2,3, 3,2,3,2, 4,3,2,1, 5,4,1,2, respectively.
LetW′=u1,u4,u7. Then, the representations of the vertices vi:12≤i≤n of Gn1,4 with respect to W′ and the vertex u10 are calculated as follows:(33)rviW′≡i2,i−62,i−82,ifiis divisible by4and12≤i≤n+92,n−i+32,n−i+92,n−i+112,ifiis divisible by4andn+92+1≤i≤n,i−32,i−52,n−i+112,ifi−1is divisible by4and13≤i≤n+92,n−i+62,n−i+82,n−i+102,ifi−1is divisible by4andn+92+1≤i≤n,i−32,i−42,i−62,ifi−2is divisible by4and14≤i≤n+92,n−i+52,n−i+72,n−i+92,ifi−2is divisible by4andn+92+1≤i≤n,i−12,i−32,i−92,ifi−3is divisible by4and15≤i≤n−12,n−i+42,n−i+62,n−i+122,ifi−3is divisible by4andn−12+1≤i≤n,rviv10=i−62,ifiis divisible by4andi=12,i−102,ifiis divisible by4and13≤i≤n+172,n−i+122,ifiis divisible by4andn+172+1≤i≤n,i−92,ifi−1is divisible by4and13≤i≤n+172+1,n−i+122,ifi−1is divisible by4andn+172+2≤i≤n,i−122,ifi−2is divisible by4and14≤i≤n+172+3,n−i+152,ifi−2is divisible by4andn+172+4≤i≤n,i−112,ifi−3is divisible by4and15≤i≤n+172+3,n−i+142,ifi−3is divisible by4andn+172+4≤i≤n.
The representations of the verticesui:1≤i≤11 of Gn1,4 are calculated as follows: ru2,W=3,4,3,4, ru3,W=4,3,2,5, ru5,W=2,3,4,3, ru6,W=3,4,3,2, ru8,W=5,2,3,4, ru9,W=4,3,4,3, ru11,W=6,5,2,3, run−2,W=3,4,5,6, run−1,W=4,3,4,7, run,W=3,2,5,6.
The remaining verticesui:12≤i≤n of Gn1,4 have the following representation with respect to W′, and the vertex u10 is calculated as follows:(34)ruiW′=i+72,i−42,i−62,ifiis divisible by4and12≤i≤n+72,n−i+112,n−i+72,n−i+92,ifiis divisible by4andn+72+1≤i≤n−3,i−12,i−32,i−52,ifi−1is divisible by4and13≤i≤n+72,n−i+32,n−i+62,n−i+72,ifi−1is divisible by4andn+72+1≤i≤n−3,i+62,i−22,i−42,ifi−2is divisible by4and14≤i≤n+72,n−i+52,n−i+52,n−i+72,ifi−2is divisible by4andn+72+1≤i≤n−3,n−i2,i+52,i−72,ifi−3is divisible by4and15≤i≤n+72,n−i+42,n−i+42,n−i+102ifi−3is divisible by4andn+72+1≤i≤n−3,ruiu10=i−42,ifiis divisible by4andi=12,i−62,ifiis divisible by4and13≤i≤n+92+4,n−i+112,ifiis divisible by4andn+92+5≤i≤n−3,i−72,ifi−1is divisible by4and13≤i≤n+92+1,n−i+102,ifi−1is divisible by4andn+92+2≤i≤n−3,i−102,ifi−2is divisible by4and14≤i≤n+92+6,n−i+132,ifi−2is divisible by4andn+92+7≤i≤n−3,i−92,ifi−3is divisible by4and15≤i≤n+92+3,n−i+122,ifi−3is divisible by4andn+92+4≤i≤n−3.
One can easily verify that each vertex ofGn1,4 has unique representation with respect to W. Hence, W is a resolving set, and(35)βGn1,3≤4.
Now, to prove the lower bound, it is sufficient to show that there is no resolving set ofGn1,4 with three elements. Suppose, on contrary, that W is a minimum resolving set of Gn1,4 of cardinality 3. Define(36)A=u4i−3,v4i+1,1≤i≤n−12,B=u4i−2,v4i+2,1≤i≤n−12,C=u4i−1,v4i+3,1≤i≤n−12,D=u4i,v4i+4,1≤i≤n−12.
It is easy to see that these are disjoint subsets of the vertex set ofGn1,4. We make the following claims.Claim 3.
Letx be an arbitrary vertex of the resolving set W that does not belong to A. Then,(37)dvi−1,x=dui−4,x=i+22ori+42.
Thus, to resolveui−4 and vi−1, either ui−4 or vi−1 or one of the vertices from the set A=u4i−3,v4i+1,1≤i≤n−1/2 must belong to W.Claim 4.
Letx be an arbitrary vertex of the resolving set W that does not belong to B. Then,(38)dvi,x=dui−3,x=i2ori+22.
Thus, to resolveui−3 and vi, either ui−3 or vi or one of the vertices from the set B=u4i−2,v4i+2,1≤i≤n−1/2 must belong to W.Claim 5.
Letx be an arbitrary vertex of the resolving set W that does not belong to C. Then,(39)dvi+1,x=dui+2,x=i−12ori+12.
Thus, to resolveui+2 and vi+1, either ui+2 or vi+1 or one of the vertices from the set C=u4i−1,v4i+3,1≤i≤n−1/2 must belong to W.Claim 6.
Letx be an arbitrary vertex of the resolving set W that does not belong to D. Then,(40)dvi+2,x=dui−1,x=i−22ori2.
Thus, to resolveui−3 and vi+2, either ui−1 or vi+2 or one of the vertices from the set D=u4i,v4i+4,1≤i≤n−1/2 must belong to W.
The above claims imply thatW contains at least four elements. Thus,(41)βGn1,4≥4.
From equations (35) and (41), we get(42)βGn1,4=4.


## 2.1. IfW Contains Both Vertices from vi

One can suppose without losing any generality thatW=v1,vj:2≤j≤n. However, in this case, if j≡2mod3, then(8)ruj,W=rvj+1,W=2j3,1,for2≤j≤n2,2n−2j3,1,forn2+1≤j≤n,and if j≡0,1mod3, then(9)ruj+1,W=rvj+2,W=2j+23,2,for2≤j≤n2,2n−2j−23,2forn2+1≤j≤n.


## 2.2. IfW Contains Both Vertices from ui

One can suppose without losing any generality thatW=u1,uj:2≤j≤n. However, in this case, if j≡0mod3, then(10)ruj+1,W=rvj+2,W=2j3,3,for2≤j≤n2,2n−2j3,3,forn2+1≤j≤n,and if j≡1,2mod3,(11)ruj+3,W=rvj+4,W=2j+33,2,for2≤j≤n2,2n−2j−33,2,forn2+1≤j≤n.


## 2.3. If One Each fromvi and uj Belongs to W

One can suppose without losing any generality thatW=vi,uj:1≤i≤j≤n. However, in this case, if j≡0mod3, then(12)ruj+4,W=rvj+5,W=2j3+3,3,for3≤j≤n2−2,2n−2j−83,3,forn2−1≤j≤n,and if j≡1,2mod3,(13)ruj+3,W=rvj+4,W=2j3+2,2,for1≤j≤n2,2n−2j−63,2,forn2+1≤j≤n.Thus, there is no resolving set ofGn1,3 having two vertices. This implies that(14)βGn1,3≥3.From (7) and (14), we get(15)βGn1,3=3.Theorem 3.
Forn≥15, if n≡0,1mod3, then(16)βGn1,3=4.Proof.
LetW=v1,v2,v3,v4 be the set of vertices in Gn1,4. It is enough to show that every vertex of the graph Gn1,4 is uniquely determined by some vertices in W. For this, the representations of each vertex are calculated as follows.
The representations of outer verticesvi:1≤i≤n of Gn1,3 are calculated as follows:(17)rvi,W=2i−23,2i−43,2i−63,2i−83,for5≤i≤n+12,2n−2i+23,2n−2i+43,2n−2i+63,2n−2i+83,forn+12+4≤i≤n.
Ifi=n+1/2+1,(18)rvi,W=2i−63,2i−63,2i−63,2i−83,forn=6kandk≥3,2i−43,2i−43,2i−43,2i−73,forn=6k+1andk≥3,2i−43,2i−43,2i−63,2i−63,forn=6k+3andk≥2,2i−53,2i−33,2i−53,2i−83,forn=6k+4andk≥2.
Ifi=n+1/2+2,(19)rvi,W=2i−103,2i−83,2i−83,2i−83,forn=6kandk≥3,2i−63,2i−63,2i−63,2i−63,forn=6k+1andk≥3,2i−83,2i−63,2i−63,2i−83,forn=6k+3andk≥2,2i−103,2i−73,2i−43,2i−73forn=6k+4andk≥2.
Ifi=n+1/2+3,(20)rvi,W=2i−143,2i−123,2i−103,2i−103,forn=6kandk≥3,2i−113,2i−83,2i−83,2i−83,forn=6k+1andk≥3,2i−103,2i−103,2i−83,2i−83,forn=6k+3andk≥2,2i−123,2i−123,2i−93,2i−63,forn=6k+4andk≥2.
The verticesu1,u2,u3,u4,un−1,un have representations 1,2,2,1, 2,1,2,2, 3,2,1,2, 3,3,2,1, 2,1,2,3, 2,2,1,2, respectively.
The representations of the remaining verticesui of Gn1,3 are calculated as follows:(21)rui,W=2i+13,2i−13,2i−33,2i−53,for5≤i≤n2−1,2n−2i−13,2n−2i+13,2n−2i+33,2n−2i+53,forn2+3≤i≤n−2.
Ifi=n/2,(22)rui,W=2i−13,2i−13,2i−33,2i−33,forn=6kandk≥3,2i−23,2i+13,2i−23,2i−53,forn=6k+1andk≥3,2i−13,2i−13,2i−13,2i−43,forn=6k+3andk≥2,2i−13,2i−13,2i−13,2i−43,forn=6k+4andk≥2.
Ifi=n/2+1,(23)rui,W=2i−63,2i−43,2i−43,2i−63,forn=6kandk≥3,2i−73,2i−43,2i−13,2i−43,forn=6k+1andk≥3,2i−63,2i−43,2i−43,2i−43,forn=6k+3andk≥2,2i−33,2i−33,2i−33,2i−33,forn=6k+4andk≥2.
Ifi=n/2+2,(24)rui,W=2i−73,2i−73,2i−53,2i−53,forn=6kandk≥3,2i−93,2i−93,2i−63,2i−33,forn=6k+1andk≥3,2i−113,2i−93,2i−73,2i−73,forn=6k+3andk≥2,2i−83,2i−53,2i−53,2i−53,forn=6k+4andk≥2.
This shows that every vertex of the graphGn1,4 is uniquely determined by some of the vertices in W. Hence, W become a resolving set, and(25)βGn1,4≤4.
Letn=6k+l and l∈0,1,3,4. We show that there is no resolving set of Gn1,4 with three elements. Suppose, on contrary, that W is a minimum resolving set of Gn1,4 of cardinality 3. We have the following possibilities to choose the vertices of W.□


## 2.4. If Onlyvi∈W

One can suppose without losing any generality thatW=v1,vi,vj, where 2≤i≤3k and i+1≤j≤6k. In this case, the vertices of Gn1,4 that have the same representation for all choices of the resolving set are given as follows:(26)run−3=rvn−1=2,2i+33,2j+43,fori≡0mod3,j≡0,1mod3and for every value ofl,run+3/2=rvn+5/2=n−33,n−i+13,n−2j+53,forl=1,3andi≡0mod3,j≡2mod3,run/2=rvn+2/2=n3,n−i+13,n−2j+33,for1l=0,4andi≡0mod3,j≡2mod3,run−2=rvn=1,2i3,2j+13,otherwise and for alll.


## 2.5. If Two Vertices fromvi and One Vertex from uj Belong to W

One can suppose without losing any generality thatW=v1,vi,uj, where 2≤i≤3k and i≤j≤6k.In this case, the vertices ofGn1,4 that have the same representation for all choices of the resolving set are given as follows:(27)run−3=rvn−1=2,2i+33,2j+43,fori≡0mod3,j≡0,1mod3and for alll,run+3/2=rvn+5/2=n−33,n−i+13,n−2j+53,forl=1,3andi≡0mod3,j≡2mod3,run/2=rvn+2/2=n3,n−i+13,n−2j+33,forl=0,4andi≡0mod3,j≡2mod3,run−2=rvn=1,2i3,2j+13,otherwise and for alll.


## 2.6. If Two Vertices fromui and One Vertex from vj Belong to W

One can suppose without losing any generality thatW=v1,ui,uj, where 1≤i≤3k and i≤j≤6k.In this case, the vertices ofGn1,4 that have the same representation for all choices of the resolving set are given as follows:(28)run−3=rvn−1=2,2i+33,2j+43,fori≡0mod3,j≡0,1mod3and for alll,run+3/2=rvn+5/2=n−33,n−i+13,n−2j+53,forl=1,3andi≡0mod3,j≡2mod3,run/2=rvn+2/2=n3,n−i+13,n−2j+33,forl=0,4andi≡0mod3,j≡2mod3and forl=,run−2=rvn=1,2i3,2j+13,otherwise and for alll.


## 2.7. IfW Contains All Three Vertices from ui

One can suppose without losing any generality thatW=u1,ui,uj is a resolving set, where 2≤i≤3k and i+1≤j≤6k.In this case, the vertices ofGn1,4 that have the same representation for all choices of the resolving set are given as follows:(29)run−3=rvn−1=2,2i+33,2j+43,fori≡0mod3,j≡0,1mod3and for alll,run+3/2=rvn+5/2=n−33,n−i+13,n−2j+53,forl=1,3andi≡0mod3,j≡2mod3,run/2=rvn+2/2=n3,n−i+13,n−2j+33,forl=0,4andi≡0mod3,j≡2mod3,run−2=rvn=1,2i3,2j+13,otherwise and for alll.Thus, there is no resolving set ofGn1,4 having three elements. Hence,(30)βGn1,4≥4.From equations (25) and (30), we get(31)βGn1,4=4.Theorem 4.
Forn≥20, if n≡3mod4, then(32)βGn1,4=4.Proof.
LetW=u1,u4,u7,u10 be the set of vertices in Gn1,4. It is enough to show that every vertex of the graph Gn1,4 is uniquely determined by some vertices in W. For this, the vertices v1,…,v11 have representations 1,4,5,6, 2,3,4,5, 3,2,3,6, 2,1,4,5, 1,2,3,4, 2,3,2,3, 3,2,1,4, 4,1,2,3, 3,2,3,2, 4,3,2,1, 5,4,1,2, respectively.
LetW′=u1,u4,u7. Then, the representations of the vertices vi:12≤i≤n of Gn1,4 with respect to W′ and the vertex u10 are calculated as follows:(33)rviW′≡i2,i−62,i−82,ifiis divisible by4and12≤i≤n+92,n−i+32,n−i+92,n−i+112,ifiis divisible by4andn+92+1≤i≤n,i−32,i−52,n−i+112,ifi−1is divisible by4and13≤i≤n+92,n−i+62,n−i+82,n−i+102,ifi−1is divisible by4andn+92+1≤i≤n,i−32,i−42,i−62,ifi−2is divisible by4and14≤i≤n+92,n−i+52,n−i+72,n−i+92,ifi−2is divisible by4andn+92+1≤i≤n,i−12,i−32,i−92,ifi−3is divisible by4and15≤i≤n−12,n−i+42,n−i+62,n−i+122,ifi−3is divisible by4andn−12+1≤i≤n,rviv10=i−62,ifiis divisible by4andi=12,i−102,ifiis divisible by4and13≤i≤n+172,n−i+122,ifiis divisible by4andn+172+1≤i≤n,i−92,ifi−1is divisible by4and13≤i≤n+172+1,n−i+122,ifi−1is divisible by4andn+172+2≤i≤n,i−122,ifi−2is divisible by4and14≤i≤n+172+3,n−i+152,ifi−2is divisible by4andn+172+4≤i≤n,i−112,ifi−3is divisible by4and15≤i≤n+172+3,n−i+142,ifi−3is divisible by4andn+172+4≤i≤n.
The representations of the verticesui:1≤i≤11 of Gn1,4 are calculated as follows: ru2,W=3,4,3,4, ru3,W=4,3,2,5, ru5,W=2,3,4,3, ru6,W=3,4,3,2, ru8,W=5,2,3,4, ru9,W=4,3,4,3, ru11,W=6,5,2,3, run−2,W=3,4,5,6, run−1,W=4,3,4,7, run,W=3,2,5,6.
The remaining verticesui:12≤i≤n of Gn1,4 have the following representation with respect to W′, and the vertex u10 is calculated as follows:(34)ruiW′=i+72,i−42,i−62,ifiis divisible by4and12≤i≤n+72,n−i+112,n−i+72,n−i+92,ifiis divisible by4andn+72+1≤i≤n−3,i−12,i−32,i−52,ifi−1is divisible by4and13≤i≤n+72,n−i+32,n−i+62,n−i+72,ifi−1is divisible by4andn+72+1≤i≤n−3,i+62,i−22,i−42,ifi−2is divisible by4and14≤i≤n+72,n−i+52,n−i+52,n−i+72,ifi−2is divisible by4andn+72+1≤i≤n−3,n−i2,i+52,i−72,ifi−3is divisible by4and15≤i≤n+72,n−i+42,n−i+42,n−i+102ifi−3is divisible by4andn+72+1≤i≤n−3,ruiu10=i−42,ifiis divisible by4andi=12,i−62,ifiis divisible by4and13≤i≤n+92+4,n−i+112,ifiis divisible by4andn+92+5≤i≤n−3,i−72,ifi−1is divisible by4and13≤i≤n+92+1,n−i+102,ifi−1is divisible by4andn+92+2≤i≤n−3,i−102,ifi−2is divisible by4and14≤i≤n+92+6,n−i+132,ifi−2is divisible by4andn+92+7≤i≤n−3,i−92,ifi−3is divisible by4and15≤i≤n+92+3,n−i+122,ifi−3is divisible by4andn+92+4≤i≤n−3.
One can easily verify that each vertex ofGn1,4 has unique representation with respect to W. Hence, W is a resolving set, and(35)βGn1,3≤4.
Now, to prove the lower bound, it is sufficient to show that there is no resolving set ofGn1,4 with three elements. Suppose, on contrary, that W is a minimum resolving set of Gn1,4 of cardinality 3. Define(36)A=u4i−3,v4i+1,1≤i≤n−12,B=u4i−2,v4i+2,1≤i≤n−12,C=u4i−1,v4i+3,1≤i≤n−12,D=u4i,v4i+4,1≤i≤n−12.
It is easy to see that these are disjoint subsets of the vertex set ofGn1,4. We make the following claims.Claim 3.
Letx be an arbitrary vertex of the resolving set W that does not belong to A. Then,(37)dvi−1,x=dui−4,x=i+22ori+42.
Thus, to resolveui−4 and vi−1, either ui−4 or vi−1 or one of the vertices from the set A=u4i−3,v4i+1,1≤i≤n−1/2 must belong to W.Claim 4.
Letx be an arbitrary vertex of the resolving set W that does not belong to B. Then,(38)dvi,x=dui−3,x=i2ori+22.
Thus, to resolveui−3 and vi, either ui−3 or vi or one of the vertices from the set B=u4i−2,v4i+2,1≤i≤n−1/2 must belong to W.Claim 5.
Letx be an arbitrary vertex of the resolving set W that does not belong to C. Then,(39)dvi+1,x=dui+2,x=i−12ori+12.
Thus, to resolveui+2 and vi+1, either ui+2 or vi+1 or one of the vertices from the set C=u4i−1,v4i+3,1≤i≤n−1/2 must belong to W.Claim 6.
Letx be an arbitrary vertex of the resolving set W that does not belong to D. Then,(40)dvi+2,x=dui−1,x=i−22ori2.
Thus, to resolveui−3 and vi+2, either ui−1 or vi+2 or one of the vertices from the set D=u4i,v4i+4,1≤i≤n−1/2 must belong to W.
The above claims imply thatW contains at least four elements. Thus,(41)βGn1,4≥4.
From equations (35) and (41), we get(42)βGn1,4=4.


## 3. Conclusion

The resolvability of the circulant graphsCn1,2,…,k has been investigated by different authors [15, 17, 18, 25]. The resolvability of barycentric subdivision of circulant graphs was investigated by Imran et al. in [8, 25], where they showed that some of these families had constant metric dimension. In this paper, we have studied the metric dimension of subdivision of circulant graphs Cn1,k denoted by Gn1,k for 2≤k≤4. It is proved that the metric dimension of this family of graphs Gn1,k has unbounded metric dimension when n≥9 and k=2. It is also shown that for k = 3 and 4, the graph Gn[1,k] has constant metric dimension. This family of graphs Gn1,k which is obtained from subdivision of circulant graphs has interesting metric properties. The family has an unbounded metric dimension for k=2 and bounded metric dimension for k=3,4. We also believe that the metric dimension increases as the value of k increases. In this context, we arise the following open question.Open problem: compute the exact value of metric dimension or determine some good bounds in terms of other graphical parameters for the subdivision of circulant graphsGn1,k when k≥5. Also, characterize the classes of Gn1,2,…,k that has bounded or unbounded metric dimension.



---

*Source: 4197678-2020-09-14.xml*