# 2-Restricted Edge Connectivity of Wheel Networks

Authors: Wei Feng; Shiying Wang
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Theg-restricted edge connectivity (g-REC) is an efficient index in evaluating the reliability and fault tolerance of large-scale processing systems. Assume that G=V,E is a simple connected graph and F⊆E. The g-REC of G, denoted by λgG, is the minimum F such that G−F is disconnected and any component has at least g nodes. The n-dimensional wheel network CWn, a kind of Cayley graph, possesses many desired features. In this paper, we establish that λ2CWn is 4n−6 for n≥5, and CWn is λ2-optimal.


---

## Body

## 1. Introduction

With the increase of interconnection networks’ scale, the probability of processors and/or links’ failing increases. How to evaluate the reliability and fault tolerance of a large-scale processing system has become a significant research topic. A graphG=V,E can be always used to represent a practical interconnection network, where V (resp. E) represents the set of all processors (resp. links). One of the classical measurements for evaluating the reliability and fault tolerance of a network is edge connectivity λG of a graph G. Generally, the larger the λG is, the more reliable the responding network is. However, this index has its shortcoming, that is, it tacitly supposes that each edge incidents with the same node in G may fail simultaneously. It is very unlikely in the process of applications of large-scale networks.One of methods for compensating this deficiency is to increase certain conditions in each component ofG−S in the concept of λG. The g-restricted edge connectivity (g-REC) was introduced by Fàbrega and Fiol [1]. Assume that G=V,E is a simple connected graph and F⊆E. The g-REC of G, denoted by λgG, is the minimum F such that G−F is disconnected and any component has at least g nodes. Clearly, if G≠K1, then λ1G=λG. In particular, λ2G is equal to the conditional edge connectivity λ′G introduced in [2]. In [3], it is shown that the larger λ2G is, the more reliable the corresponding network is. Esfahanian et al. [2] have established that λ2G can be found by solving no more than Δδ+|EG|−2 network flow problems and λG≤λ2G≤ξG if λ2G exists, where ξG=mindx+dy−2:xy∈EG. A graph G with λ2G=ξG is called a λ2-optimal graph. 2-REC and λ2-optimal graph have been discussed by many researchers [4–8].


## 2. Preliminaries

### 2.1. Terminology and Notations

For those terminology and notations not stated here, the readers can refer to [9, 10]. Suppose that G=V,E is an undirected and simple graph. For any node u∈VG, define NGu=v∈VG:uv∈EG (resp. NEGu=e∈EG|e is incident with u in G) to be the neighborhood (resp. edge neighborhood) of u in G. The degree dGu of a node u is NGu. δG=mindu|u∈V (resp. ΔG=maxdu|u∈V) is the minimum (resp. maximum) degree of a graph G. For any W⊆V, let NGW=∪u∈WNGu\W. The length of a shortest cycle of G is defined as the girth of G. For X⊂V, let GX represent the induced subgraph of X in G. For X,Y⊆VG, let X,Y=xy:x∈X,y∈Y and xy∈EG. If dGu=k, for any u∈VG, then the graph G is k-regular. The subscript G of NGu,NEGu,dGu, and NGW are usually omitted if G is already known from the context. A graph G is node transitive if there exist τ∈ΓG such that τx=y, for ∀x,y∈VG, where ΓG is the automorphism group of G. Considering two graphs G1 and G2, G1≅G2 means that they are isomorphic.


### 2.2. The Wheel Networks

Assume thatQ is a finite group. Suppose that a spanning set S of Q satisfies I∉S, where I is the identity element of Q. A directed Cayley graph CayS,Q can be stated as follows: its node set is Q, and its directed arc set is q,qs:q∈Q,s∈S. If s−1∈S holds for ∀s∈S, then CayS,Q is an undirected graph.Assume thatH is a connected and simple graph and VH=1,2,…,nn≥3. If we consider each edge in H as a transposition of the symmetric graph Sn, then the edge set of H can correspond exactly to a transposition set S in Sn. From this sense, H is usually called a transposition simple graph. The Cayley graph Cay S,S is called the corresponding Cayley graph of H, also denoted by Cay H,S. By Akers et al. [11], S=Sn. If H is a tree (resp. path, star), then the corresponding Cayley graph, denoted by CΓn (resp. Bn, Sn) is called a transposition tree (resp. bubble-sort graph, star graph) [11]. If H=SEnn≥3, where VSEn=1,2,…,n and ESEn=1,i:2≤i≤n∪i,i+1:2≤i≤n−1, then the corresponding Cayley graph CaySEn,Sn, denoted by BSn, is called a bubble-sort star graph [12]. If H=Wnn≥4, where VWn=1,2,…,n and EWn=1,i:2≤i≤n∪i,i+1:2≤i≤n−1∪2,n, then the corresponding Cayley graph CayWn,Sn, denoted by CWn, is called a n-dimensional wheel network [13]. In other words, VCWn = Sn. And, for any u,v∈VCWn, uv∈ECWn iff u=v1,i, 2≤i≤n, or u=vi,i+1, 2≤i≤n−1, or u=v2,n. The diameters of BSn and CWn are both ⌊3n−1/2⌋, where n≥7 [12, 14]. BSn can be embedded in a CWn. CWn surpasses BSn in connectivity [15, 16]. Hence, CWn is also a desirable processing model. CWn is studied by many researchers [13, 14, 17–25]. CWn for n=4 has been depicted in Figure 1.Figure 1
The wheel network CW4.The permutation12⋯np1p2⋯pn can be conveniently denoted by p1p2⋯pn. Let τ and σ be two permutations. The product στ means the composition function τ followed by σ, for example, 1213=132.If we delete the node labelingn in the transposition simple graph of CWn, then a graph SEn−1 on node set 1,2,…,n−1 is obtained. Note that the Cayley graph responding SEn−1 is BSn−1. Hence, CWn can be decomposed into n copies of BSn−1 as follows. For any i∈1,2,…,n, suppose that CWni is the subgraph of CWn induced by the following node set u1u2,…,un−1i|u1u2,…,un−1 ranges over any permutations of 1,2,…,n∖i. Hence, CWni≅BSn−1. For any v∈VCWni, then three neighbors v1n, vn−1,n, and v2n of v are all called outside neighbors of v, denoted by v+=v1n, v−=vn−1,n, and v∗=v2n, respectively. An edge uv is called a cross-edge in the given decomposition if u,v are in distinct CWni’s.Proposition 1.
(see [9]). κG≤λG≤δG.Lemma 1.
(see [15]). κBSn=2n−3, ∀n≥4.Proposition 2.
(see [12]). BSn is 2n−3-regular, ∀n≥4.Proposition 3.
(see [26]). ∀n≥4, CWn is 2n−2-regular, node transitive.Proposition 4.
(see [26]). ∀n≥4, CWn is bipartite.Proposition 5.
(see [16]). ∀v∈VCWni, where i∈1,2,…,n. Then, v+, v−, and v∗ belong to 3 distinct CWnj’s j≠i.Proposition 6.
(see [16]). The number of independent cross-edges between two distinct CWni’s is 3n−2!.Proposition 7.
(see [27]). For u,v∈VCWni, where i∈1,2,…,n, then u+,u−,u∗∩v+,v−,v∗=∅.Lemma 2.
(see [2]). λG≤λ2G≤ξG.


## 2.1. Terminology and Notations

For those terminology and notations not stated here, the readers can refer to [9, 10]. Suppose that G=V,E is an undirected and simple graph. For any node u∈VG, define NGu=v∈VG:uv∈EG (resp. NEGu=e∈EG|e is incident with u in G) to be the neighborhood (resp. edge neighborhood) of u in G. The degree dGu of a node u is NGu. δG=mindu|u∈V (resp. ΔG=maxdu|u∈V) is the minimum (resp. maximum) degree of a graph G. For any W⊆V, let NGW=∪u∈WNGu\W. The length of a shortest cycle of G is defined as the girth of G. For X⊂V, let GX represent the induced subgraph of X in G. For X,Y⊆VG, let X,Y=xy:x∈X,y∈Y and xy∈EG. If dGu=k, for any u∈VG, then the graph G is k-regular. The subscript G of NGu,NEGu,dGu, and NGW are usually omitted if G is already known from the context. A graph G is node transitive if there exist τ∈ΓG such that τx=y, for ∀x,y∈VG, where ΓG is the automorphism group of G. Considering two graphs G1 and G2, G1≅G2 means that they are isomorphic.


## 2.2. The Wheel Networks

Assume thatQ is a finite group. Suppose that a spanning set S of Q satisfies I∉S, where I is the identity element of Q. A directed Cayley graph CayS,Q can be stated as follows: its node set is Q, and its directed arc set is q,qs:q∈Q,s∈S. If s−1∈S holds for ∀s∈S, then CayS,Q is an undirected graph.Assume thatH is a connected and simple graph and VH=1,2,…,nn≥3. If we consider each edge in H as a transposition of the symmetric graph Sn, then the edge set of H can correspond exactly to a transposition set S in Sn. From this sense, H is usually called a transposition simple graph. The Cayley graph Cay S,S is called the corresponding Cayley graph of H, also denoted by Cay H,S. By Akers et al. [11], S=Sn. If H is a tree (resp. path, star), then the corresponding Cayley graph, denoted by CΓn (resp. Bn, Sn) is called a transposition tree (resp. bubble-sort graph, star graph) [11]. If H=SEnn≥3, where VSEn=1,2,…,n and ESEn=1,i:2≤i≤n∪i,i+1:2≤i≤n−1, then the corresponding Cayley graph CaySEn,Sn, denoted by BSn, is called a bubble-sort star graph [12]. If H=Wnn≥4, where VWn=1,2,…,n and EWn=1,i:2≤i≤n∪i,i+1:2≤i≤n−1∪2,n, then the corresponding Cayley graph CayWn,Sn, denoted by CWn, is called a n-dimensional wheel network [13]. In other words, VCWn = Sn. And, for any u,v∈VCWn, uv∈ECWn iff u=v1,i, 2≤i≤n, or u=vi,i+1, 2≤i≤n−1, or u=v2,n. The diameters of BSn and CWn are both ⌊3n−1/2⌋, where n≥7 [12, 14]. BSn can be embedded in a CWn. CWn surpasses BSn in connectivity [15, 16]. Hence, CWn is also a desirable processing model. CWn is studied by many researchers [13, 14, 17–25]. CWn for n=4 has been depicted in Figure 1.Figure 1
The wheel network CW4.The permutation12⋯np1p2⋯pn can be conveniently denoted by p1p2⋯pn. Let τ and σ be two permutations. The product στ means the composition function τ followed by σ, for example, 1213=132.If we delete the node labelingn in the transposition simple graph of CWn, then a graph SEn−1 on node set 1,2,…,n−1 is obtained. Note that the Cayley graph responding SEn−1 is BSn−1. Hence, CWn can be decomposed into n copies of BSn−1 as follows. For any i∈1,2,…,n, suppose that CWni is the subgraph of CWn induced by the following node set u1u2,…,un−1i|u1u2,…,un−1 ranges over any permutations of 1,2,…,n∖i. Hence, CWni≅BSn−1. For any v∈VCWni, then three neighbors v1n, vn−1,n, and v2n of v are all called outside neighbors of v, denoted by v+=v1n, v−=vn−1,n, and v∗=v2n, respectively. An edge uv is called a cross-edge in the given decomposition if u,v are in distinct CWni’s.Proposition 1.
(see [9]). κG≤λG≤δG.Lemma 1.
(see [15]). κBSn=2n−3, ∀n≥4.Proposition 2.
(see [12]). BSn is 2n−3-regular, ∀n≥4.Proposition 3.
(see [26]). ∀n≥4, CWn is 2n−2-regular, node transitive.Proposition 4.
(see [26]). ∀n≥4, CWn is bipartite.Proposition 5.
(see [16]). ∀v∈VCWni, where i∈1,2,…,n. Then, v+, v−, and v∗ belong to 3 distinct CWnj’s j≠i.Proposition 6.
(see [16]). The number of independent cross-edges between two distinct CWni’s is 3n−2!.Proposition 7.
(see [27]). For u,v∈VCWni, where i∈1,2,…,n, then u+,u−,u∗∩v+,v−,v∗=∅.Lemma 2.
(see [2]). λG≤λ2G≤ξG.


## 3. 2-REC ofn-Dimensional Wheel Network λ2CWn

Theorem 1.
λ2CWn=4n−6, for n≥4, and CWn is a λ2-optimal graph.Proof.
By Propositions3 and 4, we can obtain ξCWn=4n−6. By Lemma 2, λ2CWn≤4n−6, for n≥4. Next, we prove λ2CWn≥4n−6, for n≥4.
We decomposeCWn into n disjoint BSn−1 copies CWn1,CWn2,…,CWnn as above, where each CWni≅BSn−1. Assume that F is any edge subset of CWn with F≤4n−7 such that CWn−F has no isolated nodes. We just need to prove that CWn−F is connected. Assume that Fi=F∩ECWni, Ei,j=VCWni,VCWnj, and Fi,j=Ei,j∩F. Clearly, F=∪i=1nFi∪∪1≤i≠j≤nFi,j. We partition CWn into two parts: S1 and S2, where S1=CWni:Fi≥2n−5 and S2=CWni:Fi≤2n−6. Obviously, S1+S2=n. Let G˜=CWnV∪CWni∈S2CWni−F. We distinguish two cases for n.Case 1.
n≥5.Claim 1.
IfS2≠∅, then G˜ is connected.Proof.
Note thatFi corresponding to CWni in S2 satisfies that Fi≤2n−6. By Propositions 1 and 2 and Lemma 1, λCWni=λBSn−1=2n−1−3=2n−5, for i∈1,2,…,n. Hence, every CWni−Fi is connected, for any CWni in S2. By Proposition 6 and 3n−2!>4n−7≥F for n≥5, hence, CWni−Fi is connected to CWnj−Fj for any two distinct CWni and CWnj in S2. We deduce that G˜ is connected. Claim 1 is completed.
Since3×2n−5>4n−7≥F, for n≥5, we have that S1≤2. We prove that CWn−F is connected in the following situations.Case 1.1.
S1=0,S2=n.
Using a proof similar to that in Claim1, we can yield that CWn−F=G˜ is connected.Case 1.2.
S1=1, S2=n−1.
LetCWni be the only one BSn−1 copy satisfying Fi≥2n−5. Let C be any component of CWni−Fi. Next, we prove that C is connected to G˜. Note that CWn−F has no isolated nodes. If C contains only a node u, then u is connected to G˜ by one of uu+, uu−, and uu∗. If C≥2, then C has an edge uv∈ECWni−F. Let NCWniu=u1,u2,…,u2n−6,v and NCWniv=v1,v2,…,v2n−6,u. By Propositions 5 and 7, there is a path P in uuiui+,uuiui−,uuiui∗,vvivi+,vvivi−,vvivi∗∪uu+,uu−,uu∗,vv+,vv−,vv∗ such that EP∩F=∅. So, C is connected to G˜ by P. We deduce that CWn−F is connected.Case 1.3.
S1=2 and S2=n−2.
LetCWni,CWnj be just the two BSn−1 copies satisfying Fi,Fj≥2n−5. It is easy to see that 2n−5≤Fi,Fj≤4n−7−2n−5=2n−2 and F∖Fi∖Fj≤4n−7−22n−5=3. Note that Fi+Fk+Fi,k≤2n−2+3=2n+1<Ei,j=3n−2! for n≥5, where CWnk corresponding to Fk belongs to S2. We have that CWni−Fi and CWnk−Fk are connected. Similarly, we can deduce that CWnj−Fj and CWnk−Fk are connected. By Claim 1, CWn−F is connected.Case 2.
n=4.
Since4×2n−5>4n−7≥F for n=4, we have that S1≤3. We prove that CW4−F is connected in the following cases:Case 2.1.
S1=0 and S2=4.
Using a proof similar to that in Claim1, we can deduce that CW4i−Fi is connected for 1≤i≤4. We say that G˜ is connected. Otherwise, there are CW4i−Fi and CW4j−Fj, and they are disconnected, where CW4i−Fi and CW4j−Fj are both in S2. By Proposition 6, Fi,j=Ei,j=3n−2!=3×4−2!=6. Note that F≤4n−7=4×4−7=9. Hence, there is a BS4−1 copy CW4k in S2 such that Fi,k<Ei,k and Fj,k<Ej,k, where k∈1,2,3,4∖i,j. We obtain that CW4i−Fi and CW4j−Fj are both connected to CW4k−Fk. Therefore, we have that CW4−F is connected.Case 2.2.
S1=1 and S2=3.
LetCW4i be the only one BS4−1 copy satisfying Fi≥2n−5=2×4−5=3. Using a proof similar to that in Claim 1, we can include that CW4j−Fj is connected for each CW4j in S2. We say that G˜ is connected. Otherwise, there are CW4j−Fj and CW4k−Fk in S2, and they are disconnected in CW4. By Proposition 6, we have that Fj,k=Ej,k=3n−2!=3×4−2!=6. Note that F∖Fi≤6 holds clearly. Hence, there is a BS4−1 copy CW4l in S2 such that Fj,l<Ej,l and Fk,l<Ek,l, where l∈1,2,3,4∖i,j,k. We obtain that CW4j−Fj and CW4k−Fk are both connected to CW4l−Fl. Therefore, we have that G˜ is connected.
LetC be any component of CW4i−Fi. Next, we prove that C is connected to G˜. If C contains only a node u, then u is connected to G˜ by one of uu+, uu−, and uu∗, since CW4−F has no isolated nodes. If C≥2, then C has an edge uv∈ECWni−F. Let NCW4iu=u1,u2,v and NCW4iv=v1,v2,u. By Propositions 5 and 7, there is a path P in uuiui+,uuiui−,uuiui∗,vvivi+,vvivi−,vvivi∗∪uu+,uu−,uu∗,vv+,vv−,vv∗ such that EP∩F=∅, where i∈1,2. So, C is connected to G˜ by P. We deduce that CW4−F is connected.Case 2.3.
S1=2 and S2=2.
LetCW4i,CW4j be just the two BS4−1 copies satisfying Fi,Fj≥2n−5=2×4−5. Using a proof similar to that in Claim 1, we include that CW4k−Fk is connected for each CW4k in S2. Clearly, F∖Fi∖Fj≤4n−7−2n−5=3<34−2!=Ek,l, where k,l∈1,2,3,4∖i,j. By Proposition 6, G˜ is connected.Case 2.3.1.
BothCW4i−Fi and CW4j−Fj are connected.
We claim thatCW4−F is connected. Otherwise, there are two copies CW4k and CW4l are disconnected for 1≤k≠l≤4. By Proposition 6, Ek,l=3n−2!=3×4−2!=6. Note that F≤4n−7=4×4−7=9. Hence, for any CW4m, m∈1,2,3,4∖k,l such that both CW4k−Fk and CW4l−Fl are connected to CW4m−Fm. We deduce that CW4−F is connected.Case 2.3.2.
Only one ofCW4i−Fi and CW4j−Fj is connected.
Assume thatCW4i−Fi be disconnected and CW4j−Fj be connected. By Proposition 6 and F∖F1∖F2≤3<6=Ej,k, CW4j−Fj is connected to CW4k−Fk, where CW4k is any one in S2. Therefore, CW4j−Fj is connected to G˜. Let C be any component of CW4i−Fi. Next, we prove that C is connected to G˜. If C contains only a node u, then u is connected to G˜ by one of uu+, uu−, and uu∗, since CW4−F has no isolated nodes. If C≥2, then C has an edge uv∈ECW4i−F. Let NCW4iu=u1,u2,v and NCWniv=v1,v2,u. By Propositions 5 and 7, there is a path P in uuiui+,uuiui−,uuiui∗,vvivi+,vvivi−,vvivi∗∪uu+,uu−,uu∗,vv+,vv−,vv∗ such that EP∩F=∅, where i∈1,2. So, C is connected to G˜ by P. We deduce that CW4−F is connected.Case 2.3.3.
NeitherCW4i−Fi nor CW4j−Fj is connected.
LetCi1,Ci2,…,Cik be all components in CW4i−Fi, and let Cj1,Cj2,…,Cjl be all components in CW4j−Fj. We consider any Cis for s∈1,2,…,k. Let u∈VCis, and we give Claim 2 as follows:Claim 2.
u is connected to G˜.Proof.
By Proposition5, it is easy to prove that, at most one cross-edge of uu+,uu−,uu∗ is in Ei,j, where j∈1,2,3,4∖i. We distinguish two cases to complete Claim 2.Case 2.3.3.1.
uu+,uu−,uu∗∩Ei,j=0.
Ifuu+,uu−,uu∗⊆F, then it is a contradiction to that CW4−F has no isolated nodes. Hence, there is an element e∈uu+,uu−,uu∗ and e∉F. By Proposition 5, u is connected to G˜ by e. Claim 2 is completed in this case.Case 2.3.3.2.
uu+,uu−,uu∗∩Ei,j=1.
Suppose thatuu+∈Ei,j. Since F1,F2≥2n−5=2×4−5 and F≤4n−7=4×4−7=9, we can deduce F∖F1∖F2≤4n−7−2n−5−2n−5=3. Note that uu+,uu−,uu∗,u+u++,u+u+−,u+u+∗=6 by Proposition 5. So, there is an element e∈uu+,uu−,uu∗,u+u++,u+u+−,u+u+∗ and e∉F such that u is connected to G˜ by e. The situations of uu−∈Ei,j and uu∗∈Ei,j can be similarly proved. Claim 2 is completed in this case.
Similarly, we can deduce that a nodev in any Cjt for t∈1,2,…,l is connected to G˜. By the arbitrariness of Cis and Cjt, we prove that each of Ci1,Ci2,…,Cik,Cj1,Cj2,…,\\Cjl is connected to G˜. So, CW4−F is connected.Case 2.4.
S1=3 and S2=1.
LetCW4i,CW4j,CW4k be just the three BS4−1 copies satisfying Fi,Fj,Fk≥2n−5=2×4−5=3. It implies that Fi=Fj=Fk=3 since F≤4n−7=4×4−7=9. Hence, there is no edges of F in ECW4∖ECW4i∖ECW4j∖ECW4k. It implies that F∩Fi,j=∅, for 1≤i≠j≤4, and Fl=0, for l∈1,2,3,4∖i,j,k. Note that Fi+Fl+Fi,l=3<6=3n−2!=Ei,l. Hence, CW4j−Fj and CW4l−Fl are connected. Similarly, both CW4j−Fj and CW4k−Fk are connected to CW4l−Fl. We have that CW4−F is connected.
Therefore, we establishedλ2CWn=4n−6 for n≥4. Since λ2CWn=ξCWn, we say that CWn is a λ2-optimal graph. The theorem is completed.


## 4. Conclusion

Theg-restricted edge connectivity is a generalization of classical edge connectivity. It is a more refined index in measuring fault tolerance of interconnection networks. Here, we obtain that 2-restricted edge connectivity of wheel network CWn. Note that wheel network CWn is a kind of regular graph. A nontrivial graph with order n whose degree set contains n−1 elements is named an antiregular graph [28]. It would be interesting to find the g-restricted edge connectivity of antiregular graphs.



---

*Source: 3725778-2021-07-06.xml*