# Computing Minimal Doubly Resolving Sets and the Strong Metric Dimension of the Layer Sun Graph and the Line Graph of the Layer Sun Graph

Authors: Jia-Bao Liu; Ali Zafari
Journal: Complexity
 (2020)

---

## Abstract

LetG be a finite, connected graph of order of, at least, 2 with vertex set VG and edge set EG. A set S of vertices of the graph G is a doubly resolving set for G if every two distinct vertices of G are doubly resolved by some two vertices of S. The minimal doubly resolving set of vertices of graph G is a doubly resolving set with minimum cardinality and is denoted by ψG. In this paper, first, we construct a class of graphs of order 2n+Σr=1k−2nmr, denoted by LSGn,m,k, and call these graphs as the layer Sun graphs with parameters n, m, and k. Moreover, we compute minimal doubly resolving sets and the strong metric dimension of the layer Sun graph LSGn,m,k and the line graph of the layer Sun graph LSGn,m,k.


---

## Body

## 1. Introduction

In this paper, supposeG is a finite, simple connected graph of order of, at least, 2, with vertex set VG and edge set EG. If x and y are vertices in the graph G, then the distance x from y in G is denoted by dGx,y or simply dx,y, where dx,y is the length of the shortest path from x to y. The line graph of a graph G is denoted by LG, with vertex set VLG=EG and where two edges of G are adjacent in LG if and only if they are incident in G, see [1]. Vertices x,y of the graph G are said to doubly resolve vertices u,v of G if du,x−du,y≠dv,x−dv,y. A set S of vertices of the graph G is a doubly resolving set of G if every two distinct vertices of G are doubly resolved by some two vertices of S. The minimal doubly resolving set of vertices of graph G is a doubly resolving set with minimum cardinality and is denoted by ψG. The notion of a doubly resolving set of vertices of the graph G was introduced by Cáceres et al. [2]. A vertex w strongly resolves two vertices u and v if u belongs to a shortest v−w path or v belongs to a shortest u−w path. A vertex set S of the graph G is a strong resolving set of G if every two distinct vertices of G are strongly resolved by some vertex of S. A strong metric basis of G is denoted by sdimG defined as the minimum cardinality of a strong resolving set of G. The notion of a strong metric dimension problem set of vertices of the graph G was introduced by A. Sebö and E. Tannier [3] and further investigated by O. R. Oellermann and Peters-Fransen [4]. The minimal doubly resolving sets for jellyfish and cocktail party graphs have been obtained in [5]. For more results related to these concepts, see [6–16]. In this paper, first, we construct a class of graphs of order 2n+Σr=1k−2nmr, denoted by LSGn,m,k, and call these graphs as the layer Sun graphs with parameters n, m, and k, which is defined as follows:Letn,m,k be integers such that n,k≥3, m≥2 and G be a graph with vertex set VG=V1∪V2∪…∪Vk, where V1,V2,…Vk are called the layers of G such that V1=VCn=1,2,…,n, V2=v1,v2,…,vn, and for l≥3, we have Vl=B11l,B12l,…,B1ml−3l;B21l,B22l,…,B2ml−3l;…;Bn1l,Bn2l,…,Bnml−3l, and let Bijl=∪t=1mvij,tl, such that every vij,tl is a vertex in the layer Vl, and Bijl≅Km¯ in the layer Vl, 1≤i≤n, 1≤j≤ml−3, 1≤t≤m, where Km¯ is the complement of the complete graph on m vertices. Now, suppose that every vertex i in the cycle Cn is adjacent to exactly one vertex in the layer V2, say vi∈V2, and every vertex vi in the layer V2 is adjacent to exactly m vertices vi1,13,vi1,23,…,vi1,m3∈Bi13∈V3, in particular for l≥3, every vertex vir,tl∈Birl∈Vl is adjacent to exactly m vertices ∪t=1mvij,tl+1∈Bijl+1∈Vl+1, and then, the resulting graph is called the layer Sun graph LSGn,m,k with parameters n, m, and k. Also, for l≥3, we recall that Bijl as the components of the layer Vl, 1≤i≤n, 1≤j≤ml−3. In particular, we say that two components Bijl,Brsl∈Vl, 1≤i,r≤n, 1≤j,s≤ml−3 are fundamental if i=r and j≠s. It is natural to consider its vertex set of the layer Sun graph LSGn,m,k as partitioned into k layers. The layers V1 and V2 consist of the vertices 1,2,…,n and v1,v2,…,vn, respectively. In particular, each layer Vll≥3 consists of the nml−2 vertices. Note that, for each vertex i in the layer V1 and every vertex x∈Bijl∈Vl, l≥3, 1≤j≤ml−3, we have di,x=l−1. In this paper, we consider the problem of determining the cardinality ψLSGn,m,k of minimal doubly resolving sets of the layer Sun graph LSGn,m,k. First, we find the metric dimension of the layer Sun graph LSGn,m,k; in fact, we prove that if n,k≥3 and m≥2, then the metric dimension of the layer Sun graph LSGn,m,k is nmk−2−nmk−3. Moreover, we consider the problem of determining the cardinality ψLSGn,m,k of minimal doubly resolving sets of LSGn,m,k and the strong metric dimension for the layer Sun graph LSGn,m,k and the line graph of the layer Sun graph LSGn,m,k. The graph LSG3,3,4 is shown in Figure 1.Figure 1
LSG(3,3,4).


## 2. Definitions and Preliminaries

Definition 1.
LetG be a graph. A vertex x∈VG is said to resolve a pair u,v∈VG if dGu,x≠dGv,x. For an ordered subset W=w1,w2,…,wk of vertices in the graph G and a vertex v of G, the metric representation of v with respect to W is the k-vector rv/W=dv,w1,dv,w2,…,dv,wk. If every pair of distinct vertices of G has different metric representations, then the ordered set W is called a resolving set of G. If the set W is as small as possible, then it is called a metric basis of the graph G. We recall that the metric dimension of G, denoted by βG, is defined as the minimum cardinality of a resolving set for G.Proposition 1.
LetG be a graph. It is well known that a doubly resolving set is also a resolving set and βG≤ψG. In particular, every strong resolving set is a resolving set and βG≤sdimG.


## 3. Main Results

### 3.1. Minimal Doubly Resolving Sets and the Strong Metric Dimension for the Layer Sun GraphLSGn,m,k

Theorem 1.
LetG=LSGn,m,k be the layer Sun graph which is defined already. Suppose that n,m,k are integers such that n,k≥3 and m≥2. Then, the metric dimension of LSGn,m,k is nmk−2−nmk−3.Proof.
LetVG=V1∪V2∪…∪Vk, where V1,V2,…,Vk are called the layers of vertices in the layer Sun graph LSGn,m,k, which is defined already. It is clear that if W is an ordered subset of the layers V1∪V2∪…∪Vk−1, then W is not a resolving set in LSGn,m,k. We may assume that the layer Vk is equal to(1)Vk=B11k,B12k,…,B1mk−3k;B21k,B22k,…,B2mk−3k;…;Bn1k,Bn2k,…,Bnmk−3k,where Bijk=∪t=1mvij,tk, 1≤i≤n, 1≤j≤mk−3. In the following cases, it can be shown that the metric dimension of the layer Sun graph LSGn,m,k is nmk−2−nmk−3.Case 1: letW be an ordered subset of the layer Vk in the layer Sun graph LSGn,m,k such that(2)W=B12k,…,B1mk−3k;B21k,B22k,…,B2mk−3k;…;Bn1k,Bn2k,…,Bnmk−3k.Hence,(3)VG−W=V1,V2,…,Vk−1,B11k.We know that the cardinality ofW is nmk−2−m because Bijk=m1≤i≤n, 1≤j≤mk−3. Therefore, the metric representation of all the vertices v11,1k,v11,2k,…,v11,mk in the component B11k is the same as nmk−2−m-vector with respect to W. Thus, W is not a resolving set in LSGn,m,kCase 2: letW be an ordered subset of the layer Vk in the layer Sun graph LSGn,m,k such that(4)W=B11k−v11,1k,v11,2k,B12k,…,B1mk−3k;B21k,B22k,…,B2mk−3k;…;Bn1k,Bn2k,…,Bnmk−3k.Hence,(5)VG−W=V1,V2,…,Vk−1,v11,1k,v11,2k.We know thatW=nmk−2−2. Therefore, the metric representation of two vertices v11,1k,v11,2k in the component B11k is the same as nmk−2−2-vector with respect to W. Thus, W is not a resolving set in LSGn,m,k.Case 3: letW be an ordered subset of the layer Vk in the layer Sun graph LSGn,m,k such that(6)W=B11k−v11,1k,B12k−v12,1k,…,B1mk−3k−v1mk−3,1k;…;Bn1k−vn1,1k,Bn2k−vn2,1k,…,Bnmk−3k−vnmk−3,1k.Hence,(7)VG−W=V1,V2,…,Vk−1,v11,1k,…,v1mk−3,1k,…,vn1,1k,…,vnmk−3,1k.We know thatW=nmk−2−nmk−3. We can show that all the vertices in VG−W have different representations with respect to W. Let u be the vertex of the layer V1=VCn=1,2,…,n. We can assume without loss of generality that u=i, 1≤i≤n. Hence, du,vij,tk=k−1, where vij,tk∈Bijk, 1≤t≤m, 1≤j≤mk−3; otherwise, if u≠i, then du,vij,tk>k−1. Now, let u∈V2=v1,v2,…,vn. We can assume without loss of generality that u=vi, 1≤i≤n. Hence, du,vij,tk=k−2, where vij,tk∈Bijk, 1≤t≤m, 1≤j≤mk−3; otherwise, if u≠vi, then du,vij,tk>k−2. In a similar way, we can show that all the vertices in the layers V3,…,Vk−1 have different representations with respect to W. In particular, for every vertex u∈v11,1k,…,v1mk−3,1k,…,vn1,1k,…,vnmk−3,1k, we have du,vij,tk=2, 2≤t≤m, if u=vij,1k; otherwise, if u∈v11,1k,…,v1mk−3,1k,…,vn1,1k,…,vnmk−3,1k and u≠vij,1k, then du,vij,tk>4. Therefore, all the vertices in VG−W have different representations with respect to W. This implies that W is a resolving set in LSGn,m,k. From the abovementioned cases, we can be concluded that the minimum possible cardinality of a resolving set in LSGn,m,k is nmk−2−nmk−3.Theorem 2.
LetG=LSGn,m,k be the layer Sun graph which is defined already. Suppose that n,m,k are integers such that n,k≥3 and m≥2. Then, the cardinality of minimum doubly resolving set of the LSGn,m,k is nmk−2.Proof.
In the following cases, it can be shown that the cardinality of minimum doubly resolving set of the layer Sun graphLSGn,m,k is nmk−2.Case 1: we know that the ordered subsetW of vertices in equation (8) in the layer Vk of LSGn,m,k is a resolving set for LSGn,m,k of cardinality nmk−2−nmk−3. We show that this subset is not a doubly resolving set for LSGn,m,k. Because if the vertex u=vij,1k∈Bijk∈Vk, 1≤i≤n, 1≤j≤mk−3 is adjacent to a vertex v∈Vk−1, then for every x,y∈W, we have du,x−du,y=dv,x−dv,y.(8)W=B11k−v11,1k,B12k−v12,1k,…,B1mk−3k−v1mk−3,1k;…;Bn1k−vn1,1k,Bn2k−vn2,1k,…,Bnmk−3k−vnmk−3,1k.Case 2: now, let the subset of vertices inLSGn,m,k be(9)W=B11k−v11,1k,B12k,…,B1mk−3k,…,Bn1k,Bn2k,…,Bnmk−3k.In a similar fashion as in Case 3 of Theorem1, we can show that all the vertices in the layers V1,V2,…,Vk−1 of LSGn,m,k and the vertex v11,1k in the layer Vk of LSGn,m,k have different representations with respect to W. So, W is a resolving set in LSGn,m,k of cardinality nmk−2−1. Note that, in this case, by a similar way as in Case 1, we can show that this subset is not a doubly resolving set for LSGn,m,k.Case 3: finally, let the subset of vertices inLSGn,m,k be(10)W=B11k,B12k,…,B1mk−3k;…;Bn1k,Bn2k,…,Bnmk−3k.In a similar fashion as in Theorem1, we can show that all the vertices in the layers V1,V2,…,Vk−1 of LSGn,m,k have different representations with respect to W. So, this subset is also a resolving set in LSGn,m,k of cardinality nmk−2. We show that this subset is a doubly resolving set for LSGn,m,k. It is sufficient to prove that for two vertices u and v in LSGn,m,k, there are vertices x,y∈W such that du,x−du,y≠dv,x−dv,y. Consider two vertices u and v in LSGn,m,k. Then, we have the following.Case 3.1: suppose that both verticesu and v lie in the layer V1. Hence, there are r,s∈1,2,…,n such that u=r and v=s. Moreover, we know that the layer Sun graph LSGn,m,k has the property that, for each vertex r in the layer V1, there is some vertex such as x=vrj,tk in the component Brjk, 1≤j≤mk−3 in the layer Vk, at distance k−1 from u; in fact, du,x=k−1. In the same way, there is some vertex such as y=vsj,tk in the component Bsjk, in the layer Vk, at distance k−1 from v. In particular, it is easy to prove that du,x−du,y<0 because du,y≥k. Also, dv,x−dv,y>0 because dv,x≥k.Case 3.2: now, suppose that both verticesu and v lie in the layer V2. In a similar way as in Case 3.1, we can show that there are vertices x,y∈W such that du,x−du,y≠dv,x−dv,y.Case 3.3: suppose that both verticesu and v lie in the layer Vl, l≥3 such that these vertices lie in the one component of the layer Vl, say Bijl, 1≤i≤n, 1≤j≤ml−3. In this case, du,v=2. Moreover, we know that the layer Sun graph LSGn,m,k has the property that, for each vertex u∈Bijl in the layer Vl, there is a component of the layer Vk, say Birk, 1≤i≤n, 1≤r≤mk−3 such that for any vertex x∈Birk, we have du,x=k−l. In the same way, for the vertex v∈Bijl in the layer Vl, there is a component of the layer Vk, say Bisk, 1≤i≤n, 1≤s≤mk−3, r≠s such that, for any vertex y∈Bisk, we have dv,y=k−l. Thus, du,x−du,y≠dv,x−dv,y because du,y=k−l+2 and dv,x=k−l+2.Case 3.4: suppose that both verticesu and v lie in the layer Vl, l≥3 such that these vertices lie in the two distinct components of the layer Vl. We can assume without loss of generality that u∈Bpj1l and v∈Bqj2l, 1≤p,q≤n, and 1≤j1,j2≤ml−3. Moreover, we know that the layer Sun graph LSGn,m,k has the property that, for each vertex u∈Bpj1l in the layer Vl, there is a component of the layer Vk, say Bprk, 1≤r≤mk−3 such that for any vertex x∈Bprk, we have du,x=k−l. In the same way, for the vertex v∈Bqj2l in the layer Vl, there is a component of the layer Vk, say Bqsk, 1≤s≤mk−3, such that for any vertex y∈Bqsk, we have dv,y=k−l. In the following, let two components Bpj1l and Bqj2l be fundamental; indeed, p=q. Hence, du,v=2l−4, du,y=dv,x=k+l−4. Thus, du,x−du,y≠dv,x−dv,y. Now, let two components Bpj1l and Bqj2l not be fundamental; indeed, p≠q. Hence, du,v=2l−2+dCnp,q, du,y=dv,x=k+l−2+dCnp,q. Thus, du,x−du,y≠dv,x−dv,y.Case 3.5: suppose that verticesu and v lie in distinct layers Va,Vb, respectively. Note that if a=1 and b=2, a=1 and b>2, or a=2 and b>2, there is nothing to do. Now, let 3≤a<b. Hence, there is a component of the layer Va, say Bija, 1≤i≤n, 1≤j≤ma−3 such that u∈Bija. Also, there is a component of the layer Vb, say Bpqb, 1≤p≤n, 1≤q≤mb−3 such that v∈Bpqb. In particular, there is a component of the layer Vk, say Birk, 1≤i≤n, 1≤r≤mk−3 such that for any vertex x∈Birk, we have du,x=k−a. Now, let i=p; if we consider y∈Bzsk, z≠i, 1≤z≤n, and 1≤s≤mk−3, then we have du,x−du,y≠dv,x−dv,y. Because du,y=k+a−2+dCni,z, dv,y=k+b−2+dCni,z and du,x≠dv,x. Note that if i≠p, then there is a component of the layer Vk, say Bpsk, 1≤p≤n, 1≤s≤mk−3 such that for any vertex y∈Bpjk, we have dv,y=k−b, and then, we have du,x−du,y≠dv,x−dv,y because du,x−du,y<0 and dv,x−dv,y>0. Thus, from the abovementioned cases, we can conclude that the cardinality of the minimum doubly resolving set of the layer Sun graph LSGn,m,k is nmk−2.Theorem 3.
LetG=LSGn,m,k be the layer Sun graph which is defined already. Suppose that n,m,k are integers such that n,k≥3 and m≥2. Then, the strong metric dimension of LSGn,m,k is nmk−2−1.Proof.
In the following cases, it can be seen that the cardinality of the minimum strong resolving set of the layer Sun graphLSGn,m,k is nmk−2−1.Case 1: we know that the ordered subsetW of vertices in equation (11) in the layer Vk of the layer Sun graph LSGn,m,k is a resolving set for LSGn,m,k of cardinality nmk−2−nmk−3. Now, let N=Vk−W=v11,1k,…,v1mk−3,1k,…,vn1,1k,…,vnmk−3,1k. By considering distinct vertices u,v∈N, we can show that there is not a vertex w∈W such that u belongs to a shortest v−w path or v belongs to a shortest u−w path because the valency of every vertex in the layer Vk is one. So, this subset is not a strong resolving set for G. Thus, we can be conclude that if W is a strong resolving set for graph G, then W≥nmk−2−1 because N must be less than 2.(11)W=B11k−v11,1k,B12k−v12,1k,…,B1mk−3k−v1mk−3,1k;…;Bn1k−vn1,1k,Bn2k−vn2,1k,…,Bnmk−3k−vnmk−3,1k,Case 2: on the other hand, we can show that the subsetW of vertices in equation (12) in the graph G is a resolving set for graph G. We show that this subset is a strong resolving set in graph G. It is sufficient to prove that every two distinct vertices u,v∈VG−W are strongly resolved by a vertex w∈W. Then, we have the following:(12)W=B11k−v11,1k,B12k,…,B1mk−3k,…,Bn1k,Bn2k,…,Bnmk−3k.Case 2.1: suppose that both verticesu and v lie in the layer V1. Hence, there are r,s∈1,2,…,n such that u=r and v=s. Moreover, we know that the layer Sun graph LSGn,m,k has the property that, for each vertex r in the layer V1, there is a component Brjk, 1≤j≤mk−3 in the layer Vk such that, for every vertex such as w∈Brjk, we have du,w=k−1 and dv,w>k−1, and hence, u belongs to a shortest w−v path.Case 2.2: now suppose that both verticesu and v lie in the layer V2. In a similar way as in Case 2.1, we can show that the vertices u and v are strongly resolved by a vertex w∈W.Case 2.3: suppose that both verticesu and v lie in the layer Vl, l≥3 such that these vertices lie in the one component of the layer Vl, say Bijl, 1≤i≤n, 1≤j≤ml−3. In this case, du,v=2. Moreover, we know that the layer Sun graph LSGn,m,k has the property that, for each vertex u∈Bijl in the layer Vl, there is a component of the layer Vk, say Birk, 1≤i≤n, 1≤r≤mk−3 such that for any vertex w∈Birk, we have du,w=k−l, and hence, u belongs to a shortest w−v path.Case 2.4: suppose that both verticesu and v lie in the layer Vl, l≥3 such that these vertices lie in the two distinct components of the layer Vl. We can assume without loss of generality that u∈Bpj1l and v∈Bqj2l, 1≤p,q≤n, and 1≤j1,j2≤ml−3. Moreover, we know that the layer Sun graph LSGn,m,k has the property that, for each vertex u∈Bpj1l in the layer Vl, there is a component of the layer Vk, say Bprk, 1≤r≤mk−3 such that for any vertex w∈Bprk, we have du,w=k−l, and hence, u belongs to a shortest w−v path.Case 2.5: suppose that verticesu and v lie in distinct layers Va,Vb, respectively. Note that if a=1 and b=2, a=1 and b>2, or a=2 and b>2, there is nothing to do. Now, let 3≤b<a. Hence, there is a component of the layer Va, say Bija, 1≤i≤n, 1≤j≤ma−3 such that u∈Bija. Also, there is a component of the layer Vb, say Bpqb, 1≤p≤n, 1≤q≤mb−3 such that v∈Bpqb. In particular, there is a component of the layer Vk, say Birk, 1≤i≤n, 1≤r≤mk−3 such that, for any vertex w∈Birk, we have du,w=k−a, and hence, u belongs to a shortest w−v path.Case 2.6: letu,v be two distinct vertices in VG−W such that u=v11,1k∈Vk and v∈Vl, l≥3. So, there is a component Brj1l in the layer Vl, 1≤r≤n and 1≤j1≤ml−3 such that v∈Brj1l. Thus, there is some vertex in the component Brj2k, 1≤j2≤mk−3 say w such that dw,v=k−l, dw,u>k−l, and v belongs to a shortest w−u path.Case 2.7: letu,v be two distinct vertices in VG−W such that u=v11,1k∈Vk and v∈V1. So, there is some i∈V1=1,2,…,n such that v=i. If i=1, indeed du,v=k−1, and then, there is a component Brjk in the layer Vk, r≠1 and 1≤j≤mk−3 such that, for every vertex such as w in the component Brjk, we have dw,v≥k, dw,u≥2k−1, and v belongs to a shortest w−u path. Now, let i≠1; indeed, du,v≥k, and hence, there is a component Bijk in the layer Vk, 1≤j≤mk−3 such that, for every vertices such as w in the components Bijk, we have dw,v=k−1, dw,u≥2k−1, and v belongs to a shortest w−u path.
Thus, from the abovementioned cases, we can be concluded that the cardinality of minimum strong resolving set of the layer Sun graphLSGn,m,k is nmk−2−1.


### 3.2. Minimal Doubly Resolving Sets and the Strong Metric Dimension for the Line Graph of Layer Sun GraphLSGn,m,k

LetG=LSGn,m,k be the layer Sun graph which is defined already. Now, let H be a graph with vertex set VH=U1∪U2∪…∪Uk, where U1,U2,…,Uk are called the layers of H which is defined as follows:LetU1=VCn=1,2,…,n and U2=u1,u2,…,un, and for l≥3, we have(13)Ul=D11l,D12l,…,D1ml−3l;D21l,D22l,…,D2ml−3l;…;Dn1l,Dn2l,…,Dnml−3l,and let Dijl=∪t=1muij,tl such that every uij,tl is a vertex in the layer Ul and Dijl≅Km in the layer Ul, 1≤i≤n, 1≤j≤ml−3, 1≤t≤m, where Km is the complete graph on m vertices. Now, suppose that every vertex i∈2,3,…,n in the cycle Cn or the layer U1 is adjacent to exactly two vertices in the layer U2 say ui,ui−1∈U2. In particular, for the vertex 1 in the layer U1, we have 1 adjacent to exactly two vertices in the layer U2, say u1,un∈U2. Also, every vertex ui in the layer U2 is adjacent to exactly m vertices ui1,13,ui1,23,…,ui1,m3∈Di13∈U3, in particular for l≥3, every vertex uir,tl∈Dirl∈Ul is adjacent to exactly m vertices ∪t=1muij,tl+1∈Dijl+1∈Ul+1, and then, the resulting graph is isomorphic with the line graph of the layer Sun graph LSGn,m,k with parameters n, m, and k; in fact, LG≅H. Note that simply we use refinement of the natural relabelling of the line graph of the graph LSGn,m,k. Also, for l≥3, we recall Dijl as the components of Ul, 1≤i≤n, 1≤j≤ml−3. In particular, we say that two components Dijl,Drsl1≤i,r≤n, 1≤j,s≤ml−3 are fundamental if i=r and j≠s. It is natural to consider its vertex set of the line graph of the layer Sun graph LSGn,m,k is also as partitioned into k layers. The layers U1 and U2 consist of the vertices 1,2,…,n and u1,u2,…,un, respectively. In particular, each layer Ul (l≥3) consists of the nml−2 vertices. Note that, for each vertex i in the layer U1 and every vertex x∈Dijl∈Ul, l≥3, 1≤j≤ml−3, we have di,x=l−1. In this section, we consider the problem of determining the cardinality ψLG of minimal doubly resolving sets of the line graph of the layer Sun graph LSGn,m,k. We find the minimal doubly resolving set for the line graph of the layer Sun graph LSGn,m,k, and in fact, we prove that if n,k≥3 and m≥2, then the minimal doubly resolving set of the line graph of the layer Sun graph LSGn,m,k is nmk−2−nmk−3. Figure 2 shows the line graph of the graph LSG3,3,4. Note that simply we use refinement of the natural relabelling of the line graph of the graph LSG3,3,4.Figure 2
The line graph LSG(3,3,4).Theorem 4.
LetG=LSG3,3,4 be the layer Sun graph which is defined already. Suppose that n,m,k are integers such that n,k≥3 and m≥2. Then, the cardinality of minimum doubly resolving set in the line graph of the graph G is nmk−2−nmk−3.Proof.
LetW be an ordered subset of the layer Uk in the line graph of the graph G such that(14)W=D11k−u11,1k,D12k−u12,1k,…,D1mk−3k−u1mk−3,1k;…;Dn1k−un1,1k,Dn2k−un2,1k,…,Dnmk−3k−unmk−3,1k.
Hence,(15)VLG−W=U1,U2,…,Uk−1,u11,1k,…,u1mk−3,1k,…,un1,1k,…,unmk−3,1k.
We know thatW=nmk−2−nmk−3. In a similar way as in Theorem 1, we can show that this subset is a minimal resolving set for the line graph of the graph G. We prove that this subset is a doubly resolving set for the line graph of the graph G, and hence, βLG=ψLG. It is sufficient to prove that, for any two vertices u and v in LG, there are vertices x,y∈W such that du,x−du,y≠dv,x−dv,y. Consider two vertices u and v in LG. Then, we have the following:Case 1: suppose that both verticesu and v lie in the layer U1. Hence, there are r,s∈1,2,…,n such that u=r and v=s. Moreover, we know that the line graph of the graph G has the property that, for each vertex r in the layer U1 there is some vertex such as x=urj,tk in the component Drjk, 1≤j≤mk−3 in the layer Uk, at distance k−1 from u, and in fact, du,x=k−1. In the same way, there is some vertex such as y=usj,tk in the component Dsjk, in the layer Uk, at distance k−1 from v. In particular, it is easy to prove that du,x−du,y<0 because du,y≥k. Also, dv,x−dv,y>0 because dv,x≥k.Case 2: now, suppose that both verticesu and v lie in the layer U2. In a similar way as in Case 1, we can show that there are vertices x,y∈W such that du,x−du,y≠dv,x−dv,y.Case 3: suppose that both verticesu and v lie in the layer Ul, l≥3 such that these vertices lie in the one component of the layer Ul, say Dijl, 1≤i≤n, 1≤j≤ml−3. In this case, du,v=1. Moreover, we know that the line graph of the graph G has the property that, for each vertex u∈Dijl in the layer Ul, there is a component of the layer Uk, say Dirk, 1≤i≤n, 1≤r≤mk−3 such that, for every vertex x∈Dirk, we have du,x=k−l. In the same way, for the vertex v∈Dijl in the layer Vl, there is a component of the layer Uk, say Disk, 1≤i≤n, 1≤s≤mk−3, r≠s such that, for every vertex y∈Disk, we have dv,y=k−l. Thus, du,x−du,y≠dv,x−dv,y because du,y=k−l+1 and dv,x=k−l+1.Case 4: suppose that both verticesu and v lie in the layer Ul, l≥3 such that these vertices lie in the two distinct components of the layer Ul. We can assume without loss of generality that u∈Dpj1l and v∈Dqj2l, 1≤p,q≤n, and 1≤j1,j2≤ml−3. Moreover, we know that the line graph of the graph G has the property that, for each vertex u∈Dpj1l in the layer Ul, there is a component of the layer Uk, say Dprk, 1≤r≤mk−3 such that, for every vertex x∈Dprk, we have du,x=k−l. In the same way, for the vertex v∈Dqj2l in the layer Vl, there is a component of the layer Uk, say Dqsk, 1≤s≤mk−3, such that, for every vertex y∈Dqsk, we have dv,y=k−l. In the following, let two components Dpj1l, and Dqj2l be fundamental; indeed, p=q. Hence, du,v=2l−5, du,y=dv,x=k+l−5. Thus, du,x−du,y≠dv,x−dv,y. Now, let two components Dpj1l and Dqj2l not be fundamental; indeed, p≠q. Hence, du,v=2l−4+dU2up,uq and du,y=dv,x=k+l−4+dU2up,uq. Thus, du,x−du,y≠dv,x−dv,y.Case 5: suppose that verticesu and v lie in distinct layers Ua,Ub, respectively. Note that if a=1 and b=2, a=1 and b>2, or a=2 and b>2, there is nothing to do. Now, let 3≤a<b. Hence, there is a component of the layer Ua, say Dija, 1≤i≤n, 1≤j≤ma−3 such that u∈Dija. Also, there is a component of the layer Ub, say Dpqb, 1≤p≤n, 1≤q≤mb−3 such that v∈Dpqb. In particular, there is a component of the layer Uk, say Dirk, 1≤i≤n, 1≤r≤mk−3 such that, for any vertex x∈Dirk, we have du,x=k−a. Now, let i=p; if we consider y∈Dzsk, z≠i, 1≤z≤n, and 1≤s≤mk−3, then we have du,x−du,y≠dv,x−dv,y because du,y=k+a−4+dU2ui,uz, dv,y=k+b−4+dU2ui,uz, and du,x≠dv,x. Note that if i≠p, then there is a component of the layer Uk, say Dpsk, 1≤p≤n, 1≤s≤mk−3 such that, for any vertex y∈Dpjk, we have dv,y=k−b, and then, we have du,x−du,y≠dv,x−dv,y.
Thus, from the abovementioned cases, we conclude that the cardinality of minimum doubly resolving set in the line graph of the graphG is nmk−2−nmk−3.Theorem 5.
LetG=LSGn,m,k be the layer Sun graph which is defined already. Suppose that n,m,k are integers such that n,k≥3 and m≥2. Then, the strong metric dimension in the line graph of the graph G is nmk−2−1.Proof.
In a similar way as in the proof of Theorem3, we can show that the subset(16)W=D11k−v11,1k,D12k,…,D1mk−3k,…,Dn1k,Dn2k,…,Dnmk−3kof vertices in the line graph of the graph G is a minimal resolving set of LG.


## 3.1. Minimal Doubly Resolving Sets and the Strong Metric Dimension for the Layer Sun GraphLSGn,m,k

Theorem 1.
LetG=LSGn,m,k be the layer Sun graph which is defined already. Suppose that n,m,k are integers such that n,k≥3 and m≥2. Then, the metric dimension of LSGn,m,k is nmk−2−nmk−3.Proof.
LetVG=V1∪V2∪…∪Vk, where V1,V2,…,Vk are called the layers of vertices in the layer Sun graph LSGn,m,k, which is defined already. It is clear that if W is an ordered subset of the layers V1∪V2∪…∪Vk−1, then W is not a resolving set in LSGn,m,k. We may assume that the layer Vk is equal to(1)Vk=B11k,B12k,…,B1mk−3k;B21k,B22k,…,B2mk−3k;…;Bn1k,Bn2k,…,Bnmk−3k,where Bijk=∪t=1mvij,tk, 1≤i≤n, 1≤j≤mk−3. In the following cases, it can be shown that the metric dimension of the layer Sun graph LSGn,m,k is nmk−2−nmk−3.Case 1: letW be an ordered subset of the layer Vk in the layer Sun graph LSGn,m,k such that(2)W=B12k,…,B1mk−3k;B21k,B22k,…,B2mk−3k;…;Bn1k,Bn2k,…,Bnmk−3k.Hence,(3)VG−W=V1,V2,…,Vk−1,B11k.We know that the cardinality ofW is nmk−2−m because Bijk=m1≤i≤n, 1≤j≤mk−3. Therefore, the metric representation of all the vertices v11,1k,v11,2k,…,v11,mk in the component B11k is the same as nmk−2−m-vector with respect to W. Thus, W is not a resolving set in LSGn,m,kCase 2: letW be an ordered subset of the layer Vk in the layer Sun graph LSGn,m,k such that(4)W=B11k−v11,1k,v11,2k,B12k,…,B1mk−3k;B21k,B22k,…,B2mk−3k;…;Bn1k,Bn2k,…,Bnmk−3k.Hence,(5)VG−W=V1,V2,…,Vk−1,v11,1k,v11,2k.We know thatW=nmk−2−2. Therefore, the metric representation of two vertices v11,1k,v11,2k in the component B11k is the same as nmk−2−2-vector with respect to W. Thus, W is not a resolving set in LSGn,m,k.Case 3: letW be an ordered subset of the layer Vk in the layer Sun graph LSGn,m,k such that(6)W=B11k−v11,1k,B12k−v12,1k,…,B1mk−3k−v1mk−3,1k;…;Bn1k−vn1,1k,Bn2k−vn2,1k,…,Bnmk−3k−vnmk−3,1k.Hence,(7)VG−W=V1,V2,…,Vk−1,v11,1k,…,v1mk−3,1k,…,vn1,1k,…,vnmk−3,1k.We know thatW=nmk−2−nmk−3. We can show that all the vertices in VG−W have different representations with respect to W. Let u be the vertex of the layer V1=VCn=1,2,…,n. We can assume without loss of generality that u=i, 1≤i≤n. Hence, du,vij,tk=k−1, where vij,tk∈Bijk, 1≤t≤m, 1≤j≤mk−3; otherwise, if u≠i, then du,vij,tk>k−1. Now, let u∈V2=v1,v2,…,vn. We can assume without loss of generality that u=vi, 1≤i≤n. Hence, du,vij,tk=k−2, where vij,tk∈Bijk, 1≤t≤m, 1≤j≤mk−3; otherwise, if u≠vi, then du,vij,tk>k−2. In a similar way, we can show that all the vertices in the layers V3,…,Vk−1 have different representations with respect to W. In particular, for every vertex u∈v11,1k,…,v1mk−3,1k,…,vn1,1k,…,vnmk−3,1k, we have du,vij,tk=2, 2≤t≤m, if u=vij,1k; otherwise, if u∈v11,1k,…,v1mk−3,1k,…,vn1,1k,…,vnmk−3,1k and u≠vij,1k, then du,vij,tk>4. Therefore, all the vertices in VG−W have different representations with respect to W. This implies that W is a resolving set in LSGn,m,k. From the abovementioned cases, we can be concluded that the minimum possible cardinality of a resolving set in LSGn,m,k is nmk−2−nmk−3.Theorem 2.
LetG=LSGn,m,k be the layer Sun graph which is defined already. Suppose that n,m,k are integers such that n,k≥3 and m≥2. Then, the cardinality of minimum doubly resolving set of the LSGn,m,k is nmk−2.Proof.
In the following cases, it can be shown that the cardinality of minimum doubly resolving set of the layer Sun graphLSGn,m,k is nmk−2.Case 1: we know that the ordered subsetW of vertices in equation (8) in the layer Vk of LSGn,m,k is a resolving set for LSGn,m,k of cardinality nmk−2−nmk−3. We show that this subset is not a doubly resolving set for LSGn,m,k. Because if the vertex u=vij,1k∈Bijk∈Vk, 1≤i≤n, 1≤j≤mk−3 is adjacent to a vertex v∈Vk−1, then for every x,y∈W, we have du,x−du,y=dv,x−dv,y.(8)W=B11k−v11,1k,B12k−v12,1k,…,B1mk−3k−v1mk−3,1k;…;Bn1k−vn1,1k,Bn2k−vn2,1k,…,Bnmk−3k−vnmk−3,1k.Case 2: now, let the subset of vertices inLSGn,m,k be(9)W=B11k−v11,1k,B12k,…,B1mk−3k,…,Bn1k,Bn2k,…,Bnmk−3k.In a similar fashion as in Case 3 of Theorem1, we can show that all the vertices in the layers V1,V2,…,Vk−1 of LSGn,m,k and the vertex v11,1k in the layer Vk of LSGn,m,k have different representations with respect to W. So, W is a resolving set in LSGn,m,k of cardinality nmk−2−1. Note that, in this case, by a similar way as in Case 1, we can show that this subset is not a doubly resolving set for LSGn,m,k.Case 3: finally, let the subset of vertices inLSGn,m,k be(10)W=B11k,B12k,…,B1mk−3k;…;Bn1k,Bn2k,…,Bnmk−3k.In a similar fashion as in Theorem1, we can show that all the vertices in the layers V1,V2,…,Vk−1 of LSGn,m,k have different representations with respect to W. So, this subset is also a resolving set in LSGn,m,k of cardinality nmk−2. We show that this subset is a doubly resolving set for LSGn,m,k. It is sufficient to prove that for two vertices u and v in LSGn,m,k, there are vertices x,y∈W such that du,x−du,y≠dv,x−dv,y. Consider two vertices u and v in LSGn,m,k. Then, we have the following.Case 3.1: suppose that both verticesu and v lie in the layer V1. Hence, there are r,s∈1,2,…,n such that u=r and v=s. Moreover, we know that the layer Sun graph LSGn,m,k has the property that, for each vertex r in the layer V1, there is some vertex such as x=vrj,tk in the component Brjk, 1≤j≤mk−3 in the layer Vk, at distance k−1 from u; in fact, du,x=k−1. In the same way, there is some vertex such as y=vsj,tk in the component Bsjk, in the layer Vk, at distance k−1 from v. In particular, it is easy to prove that du,x−du,y<0 because du,y≥k. Also, dv,x−dv,y>0 because dv,x≥k.Case 3.2: now, suppose that both verticesu and v lie in the layer V2. In a similar way as in Case 3.1, we can show that there are vertices x,y∈W such that du,x−du,y≠dv,x−dv,y.Case 3.3: suppose that both verticesu and v lie in the layer Vl, l≥3 such that these vertices lie in the one component of the layer Vl, say Bijl, 1≤i≤n, 1≤j≤ml−3. In this case, du,v=2. Moreover, we know that the layer Sun graph LSGn,m,k has the property that, for each vertex u∈Bijl in the layer Vl, there is a component of the layer Vk, say Birk, 1≤i≤n, 1≤r≤mk−3 such that for any vertex x∈Birk, we have du,x=k−l. In the same way, for the vertex v∈Bijl in the layer Vl, there is a component of the layer Vk, say Bisk, 1≤i≤n, 1≤s≤mk−3, r≠s such that, for any vertex y∈Bisk, we have dv,y=k−l. Thus, du,x−du,y≠dv,x−dv,y because du,y=k−l+2 and dv,x=k−l+2.Case 3.4: suppose that both verticesu and v lie in the layer Vl, l≥3 such that these vertices lie in the two distinct components of the layer Vl. We can assume without loss of generality that u∈Bpj1l and v∈Bqj2l, 1≤p,q≤n, and 1≤j1,j2≤ml−3. Moreover, we know that the layer Sun graph LSGn,m,k has the property that, for each vertex u∈Bpj1l in the layer Vl, there is a component of the layer Vk, say Bprk, 1≤r≤mk−3 such that for any vertex x∈Bprk, we have du,x=k−l. In the same way, for the vertex v∈Bqj2l in the layer Vl, there is a component of the layer Vk, say Bqsk, 1≤s≤mk−3, such that for any vertex y∈Bqsk, we have dv,y=k−l. In the following, let two components Bpj1l and Bqj2l be fundamental; indeed, p=q. Hence, du,v=2l−4, du,y=dv,x=k+l−4. Thus, du,x−du,y≠dv,x−dv,y. Now, let two components Bpj1l and Bqj2l not be fundamental; indeed, p≠q. Hence, du,v=2l−2+dCnp,q, du,y=dv,x=k+l−2+dCnp,q. Thus, du,x−du,y≠dv,x−dv,y.Case 3.5: suppose that verticesu and v lie in distinct layers Va,Vb, respectively. Note that if a=1 and b=2, a=1 and b>2, or a=2 and b>2, there is nothing to do. Now, let 3≤a<b. Hence, there is a component of the layer Va, say Bija, 1≤i≤n, 1≤j≤ma−3 such that u∈Bija. Also, there is a component of the layer Vb, say Bpqb, 1≤p≤n, 1≤q≤mb−3 such that v∈Bpqb. In particular, there is a component of the layer Vk, say Birk, 1≤i≤n, 1≤r≤mk−3 such that for any vertex x∈Birk, we have du,x=k−a. Now, let i=p; if we consider y∈Bzsk, z≠i, 1≤z≤n, and 1≤s≤mk−3, then we have du,x−du,y≠dv,x−dv,y. Because du,y=k+a−2+dCni,z, dv,y=k+b−2+dCni,z and du,x≠dv,x. Note that if i≠p, then there is a component of the layer Vk, say Bpsk, 1≤p≤n, 1≤s≤mk−3 such that for any vertex y∈Bpjk, we have dv,y=k−b, and then, we have du,x−du,y≠dv,x−dv,y because du,x−du,y<0 and dv,x−dv,y>0. Thus, from the abovementioned cases, we can conclude that the cardinality of the minimum doubly resolving set of the layer Sun graph LSGn,m,k is nmk−2.Theorem 3.
LetG=LSGn,m,k be the layer Sun graph which is defined already. Suppose that n,m,k are integers such that n,k≥3 and m≥2. Then, the strong metric dimension of LSGn,m,k is nmk−2−1.Proof.
In the following cases, it can be seen that the cardinality of the minimum strong resolving set of the layer Sun graphLSGn,m,k is nmk−2−1.Case 1: we know that the ordered subsetW of vertices in equation (11) in the layer Vk of the layer Sun graph LSGn,m,k is a resolving set for LSGn,m,k of cardinality nmk−2−nmk−3. Now, let N=Vk−W=v11,1k,…,v1mk−3,1k,…,vn1,1k,…,vnmk−3,1k. By considering distinct vertices u,v∈N, we can show that there is not a vertex w∈W such that u belongs to a shortest v−w path or v belongs to a shortest u−w path because the valency of every vertex in the layer Vk is one. So, this subset is not a strong resolving set for G. Thus, we can be conclude that if W is a strong resolving set for graph G, then W≥nmk−2−1 because N must be less than 2.(11)W=B11k−v11,1k,B12k−v12,1k,…,B1mk−3k−v1mk−3,1k;…;Bn1k−vn1,1k,Bn2k−vn2,1k,…,Bnmk−3k−vnmk−3,1k,Case 2: on the other hand, we can show that the subsetW of vertices in equation (12) in the graph G is a resolving set for graph G. We show that this subset is a strong resolving set in graph G. It is sufficient to prove that every two distinct vertices u,v∈VG−W are strongly resolved by a vertex w∈W. Then, we have the following:(12)W=B11k−v11,1k,B12k,…,B1mk−3k,…,Bn1k,Bn2k,…,Bnmk−3k.Case 2.1: suppose that both verticesu and v lie in the layer V1. Hence, there are r,s∈1,2,…,n such that u=r and v=s. Moreover, we know that the layer Sun graph LSGn,m,k has the property that, for each vertex r in the layer V1, there is a component Brjk, 1≤j≤mk−3 in the layer Vk such that, for every vertex such as w∈Brjk, we have du,w=k−1 and dv,w>k−1, and hence, u belongs to a shortest w−v path.Case 2.2: now suppose that both verticesu and v lie in the layer V2. In a similar way as in Case 2.1, we can show that the vertices u and v are strongly resolved by a vertex w∈W.Case 2.3: suppose that both verticesu and v lie in the layer Vl, l≥3 such that these vertices lie in the one component of the layer Vl, say Bijl, 1≤i≤n, 1≤j≤ml−3. In this case, du,v=2. Moreover, we know that the layer Sun graph LSGn,m,k has the property that, for each vertex u∈Bijl in the layer Vl, there is a component of the layer Vk, say Birk, 1≤i≤n, 1≤r≤mk−3 such that for any vertex w∈Birk, we have du,w=k−l, and hence, u belongs to a shortest w−v path.Case 2.4: suppose that both verticesu and v lie in the layer Vl, l≥3 such that these vertices lie in the two distinct components of the layer Vl. We can assume without loss of generality that u∈Bpj1l and v∈Bqj2l, 1≤p,q≤n, and 1≤j1,j2≤ml−3. Moreover, we know that the layer Sun graph LSGn,m,k has the property that, for each vertex u∈Bpj1l in the layer Vl, there is a component of the layer Vk, say Bprk, 1≤r≤mk−3 such that for any vertex w∈Bprk, we have du,w=k−l, and hence, u belongs to a shortest w−v path.Case 2.5: suppose that verticesu and v lie in distinct layers Va,Vb, respectively. Note that if a=1 and b=2, a=1 and b>2, or a=2 and b>2, there is nothing to do. Now, let 3≤b<a. Hence, there is a component of the layer Va, say Bija, 1≤i≤n, 1≤j≤ma−3 such that u∈Bija. Also, there is a component of the layer Vb, say Bpqb, 1≤p≤n, 1≤q≤mb−3 such that v∈Bpqb. In particular, there is a component of the layer Vk, say Birk, 1≤i≤n, 1≤r≤mk−3 such that, for any vertex w∈Birk, we have du,w=k−a, and hence, u belongs to a shortest w−v path.Case 2.6: letu,v be two distinct vertices in VG−W such that u=v11,1k∈Vk and v∈Vl, l≥3. So, there is a component Brj1l in the layer Vl, 1≤r≤n and 1≤j1≤ml−3 such that v∈Brj1l. Thus, there is some vertex in the component Brj2k, 1≤j2≤mk−3 say w such that dw,v=k−l, dw,u>k−l, and v belongs to a shortest w−u path.Case 2.7: letu,v be two distinct vertices in VG−W such that u=v11,1k∈Vk and v∈V1. So, there is some i∈V1=1,2,…,n such that v=i. If i=1, indeed du,v=k−1, and then, there is a component Brjk in the layer Vk, r≠1 and 1≤j≤mk−3 such that, for every vertex such as w in the component Brjk, we have dw,v≥k, dw,u≥2k−1, and v belongs to a shortest w−u path. Now, let i≠1; indeed, du,v≥k, and hence, there is a component Bijk in the layer Vk, 1≤j≤mk−3 such that, for every vertices such as w in the components Bijk, we have dw,v=k−1, dw,u≥2k−1, and v belongs to a shortest w−u path.
Thus, from the abovementioned cases, we can be concluded that the cardinality of minimum strong resolving set of the layer Sun graphLSGn,m,k is nmk−2−1.


## 3.2. Minimal Doubly Resolving Sets and the Strong Metric Dimension for the Line Graph of Layer Sun GraphLSGn,m,k

LetG=LSGn,m,k be the layer Sun graph which is defined already. Now, let H be a graph with vertex set VH=U1∪U2∪…∪Uk, where U1,U2,…,Uk are called the layers of H which is defined as follows:LetU1=VCn=1,2,…,n and U2=u1,u2,…,un, and for l≥3, we have(13)Ul=D11l,D12l,…,D1ml−3l;D21l,D22l,…,D2ml−3l;…;Dn1l,Dn2l,…,Dnml−3l,and let Dijl=∪t=1muij,tl such that every uij,tl is a vertex in the layer Ul and Dijl≅Km in the layer Ul, 1≤i≤n, 1≤j≤ml−3, 1≤t≤m, where Km is the complete graph on m vertices. Now, suppose that every vertex i∈2,3,…,n in the cycle Cn or the layer U1 is adjacent to exactly two vertices in the layer U2 say ui,ui−1∈U2. In particular, for the vertex 1 in the layer U1, we have 1 adjacent to exactly two vertices in the layer U2, say u1,un∈U2. Also, every vertex ui in the layer U2 is adjacent to exactly m vertices ui1,13,ui1,23,…,ui1,m3∈Di13∈U3, in particular for l≥3, every vertex uir,tl∈Dirl∈Ul is adjacent to exactly m vertices ∪t=1muij,tl+1∈Dijl+1∈Ul+1, and then, the resulting graph is isomorphic with the line graph of the layer Sun graph LSGn,m,k with parameters n, m, and k; in fact, LG≅H. Note that simply we use refinement of the natural relabelling of the line graph of the graph LSGn,m,k. Also, for l≥3, we recall Dijl as the components of Ul, 1≤i≤n, 1≤j≤ml−3. In particular, we say that two components Dijl,Drsl1≤i,r≤n, 1≤j,s≤ml−3 are fundamental if i=r and j≠s. It is natural to consider its vertex set of the line graph of the layer Sun graph LSGn,m,k is also as partitioned into k layers. The layers U1 and U2 consist of the vertices 1,2,…,n and u1,u2,…,un, respectively. In particular, each layer Ul (l≥3) consists of the nml−2 vertices. Note that, for each vertex i in the layer U1 and every vertex x∈Dijl∈Ul, l≥3, 1≤j≤ml−3, we have di,x=l−1. In this section, we consider the problem of determining the cardinality ψLG of minimal doubly resolving sets of the line graph of the layer Sun graph LSGn,m,k. We find the minimal doubly resolving set for the line graph of the layer Sun graph LSGn,m,k, and in fact, we prove that if n,k≥3 and m≥2, then the minimal doubly resolving set of the line graph of the layer Sun graph LSGn,m,k is nmk−2−nmk−3. Figure 2 shows the line graph of the graph LSG3,3,4. Note that simply we use refinement of the natural relabelling of the line graph of the graph LSG3,3,4.Figure 2
The line graph LSG(3,3,4).Theorem 4.
LetG=LSG3,3,4 be the layer Sun graph which is defined already. Suppose that n,m,k are integers such that n,k≥3 and m≥2. Then, the cardinality of minimum doubly resolving set in the line graph of the graph G is nmk−2−nmk−3.Proof.
LetW be an ordered subset of the layer Uk in the line graph of the graph G such that(14)W=D11k−u11,1k,D12k−u12,1k,…,D1mk−3k−u1mk−3,1k;…;Dn1k−un1,1k,Dn2k−un2,1k,…,Dnmk−3k−unmk−3,1k.
Hence,(15)VLG−W=U1,U2,…,Uk−1,u11,1k,…,u1mk−3,1k,…,un1,1k,…,unmk−3,1k.
We know thatW=nmk−2−nmk−3. In a similar way as in Theorem 1, we can show that this subset is a minimal resolving set for the line graph of the graph G. We prove that this subset is a doubly resolving set for the line graph of the graph G, and hence, βLG=ψLG. It is sufficient to prove that, for any two vertices u and v in LG, there are vertices x,y∈W such that du,x−du,y≠dv,x−dv,y. Consider two vertices u and v in LG. Then, we have the following:Case 1: suppose that both verticesu and v lie in the layer U1. Hence, there are r,s∈1,2,…,n such that u=r and v=s. Moreover, we know that the line graph of the graph G has the property that, for each vertex r in the layer U1 there is some vertex such as x=urj,tk in the component Drjk, 1≤j≤mk−3 in the layer Uk, at distance k−1 from u, and in fact, du,x=k−1. In the same way, there is some vertex such as y=usj,tk in the component Dsjk, in the layer Uk, at distance k−1 from v. In particular, it is easy to prove that du,x−du,y<0 because du,y≥k. Also, dv,x−dv,y>0 because dv,x≥k.Case 2: now, suppose that both verticesu and v lie in the layer U2. In a similar way as in Case 1, we can show that there are vertices x,y∈W such that du,x−du,y≠dv,x−dv,y.Case 3: suppose that both verticesu and v lie in the layer Ul, l≥3 such that these vertices lie in the one component of the layer Ul, say Dijl, 1≤i≤n, 1≤j≤ml−3. In this case, du,v=1. Moreover, we know that the line graph of the graph G has the property that, for each vertex u∈Dijl in the layer Ul, there is a component of the layer Uk, say Dirk, 1≤i≤n, 1≤r≤mk−3 such that, for every vertex x∈Dirk, we have du,x=k−l. In the same way, for the vertex v∈Dijl in the layer Vl, there is a component of the layer Uk, say Disk, 1≤i≤n, 1≤s≤mk−3, r≠s such that, for every vertex y∈Disk, we have dv,y=k−l. Thus, du,x−du,y≠dv,x−dv,y because du,y=k−l+1 and dv,x=k−l+1.Case 4: suppose that both verticesu and v lie in the layer Ul, l≥3 such that these vertices lie in the two distinct components of the layer Ul. We can assume without loss of generality that u∈Dpj1l and v∈Dqj2l, 1≤p,q≤n, and 1≤j1,j2≤ml−3. Moreover, we know that the line graph of the graph G has the property that, for each vertex u∈Dpj1l in the layer Ul, there is a component of the layer Uk, say Dprk, 1≤r≤mk−3 such that, for every vertex x∈Dprk, we have du,x=k−l. In the same way, for the vertex v∈Dqj2l in the layer Vl, there is a component of the layer Uk, say Dqsk, 1≤s≤mk−3, such that, for every vertex y∈Dqsk, we have dv,y=k−l. In the following, let two components Dpj1l, and Dqj2l be fundamental; indeed, p=q. Hence, du,v=2l−5, du,y=dv,x=k+l−5. Thus, du,x−du,y≠dv,x−dv,y. Now, let two components Dpj1l and Dqj2l not be fundamental; indeed, p≠q. Hence, du,v=2l−4+dU2up,uq and du,y=dv,x=k+l−4+dU2up,uq. Thus, du,x−du,y≠dv,x−dv,y.Case 5: suppose that verticesu and v lie in distinct layers Ua,Ub, respectively. Note that if a=1 and b=2, a=1 and b>2, or a=2 and b>2, there is nothing to do. Now, let 3≤a<b. Hence, there is a component of the layer Ua, say Dija, 1≤i≤n, 1≤j≤ma−3 such that u∈Dija. Also, there is a component of the layer Ub, say Dpqb, 1≤p≤n, 1≤q≤mb−3 such that v∈Dpqb. In particular, there is a component of the layer Uk, say Dirk, 1≤i≤n, 1≤r≤mk−3 such that, for any vertex x∈Dirk, we have du,x=k−a. Now, let i=p; if we consider y∈Dzsk, z≠i, 1≤z≤n, and 1≤s≤mk−3, then we have du,x−du,y≠dv,x−dv,y because du,y=k+a−4+dU2ui,uz, dv,y=k+b−4+dU2ui,uz, and du,x≠dv,x. Note that if i≠p, then there is a component of the layer Uk, say Dpsk, 1≤p≤n, 1≤s≤mk−3 such that, for any vertex y∈Dpjk, we have dv,y=k−b, and then, we have du,x−du,y≠dv,x−dv,y.
Thus, from the abovementioned cases, we conclude that the cardinality of minimum doubly resolving set in the line graph of the graphG is nmk−2−nmk−3.Theorem 5.
LetG=LSGn,m,k be the layer Sun graph which is defined already. Suppose that n,m,k are integers such that n,k≥3 and m≥2. Then, the strong metric dimension in the line graph of the graph G is nmk−2−1.Proof.
In a similar way as in the proof of Theorem3, we can show that the subset(16)W=D11k−v11,1k,D12k,…,D1mk−3k,…,Dn1k,Dn2k,…,Dnmk−3kof vertices in the line graph of the graph G is a minimal resolving set of LG.


## 4. Conclusions

In this paper, we have constructed a layer Sun graphLSGn,m,k, discussed this graph, and computed the minimum cardinality of the doubly resolving set and strong resolving set of layer Sun graph LSGn,m,k and the line graph of the layer Sun graph LSGn,m,k. We deduce that, by this way, we can construct a layer jellyfish graph JFGn,m,k, of order n+Σr=1k−1nmr, where the jellyfish graph is JFGn,m, which is defined in [5], and by a similar way, we can obtain and compute the minimum cardinality of doubly resolving set and strong resolving set of layer jellyfish graph JFGn,m,k and the line graph of the layer jellyfish graph JFGn,m,k.



---

*Source: 6267072-2020-09-24.xml*