# The 2-Extra Connectivity of Wheel Networks

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

---

## Abstract

Connectivity is a significant metric for evaluating the error lenience of an interconnected netG=V,E. In the paper (Fàbrega and Fiol, 1996), the authors addressed the g-extra connectivity which is applied to better measure the consistency and error tolerance of G. As a special Cayley graph, the n-dimensional wheel network CWn has some desirable features. This paper shows that the g-extra connectivity of CWnn≥6 is 6n−12 when g=2.


---

## Body

## 1. Introduction

An interconnected net (abbreviated IN) is usually charactered as a graph, whereat each node (vertex) resembles a CPU and an edge resembles the connection between a couple of CPUs, correspondingly. Connectivity of a graphG, written as κG, is defined as the minimum number of nodes whose deletion from G implies a detached graph or has only 1 node. Connectivity is an important index in evaluating the dependability and error tolerance of an IN. The greater the connectivity is, the more consistent an IN is. Nevertheless, an understandable drawback of the index is that it adopts that each node neighboring the same node of G can flop simultaneously. In fact, it is highly unlikely in applied net uses. Hence, the traditional connectivity is inappropriate for huge computing systems.To overcome this deficiency, Harary [1] firstly presented the idea of restricted connectivity, which is a more refined index in determining the consistency and error tolerance of INs. Consider G to be a linked directionless basic graph, and p be a given 1-dimensional topology theory feature. The restricted connectivity, written as κG;p, is obtained as the minimum cardinality of a set of nodes, if any, whose deletion detaches G and each residual factor has feature p. Amid the restricted connectivity, the g-extra connectivity has been initially presented by Fàbrega and Fiol [2]. A subset S of nodes is known as a cut-set if G−S is detached. For a nonnegative integer g, a cut-set S is named a g-extra cut, if each element of G−S contains t nodes, where t≥g+1. The g-extra connectivity of G, if there must exist 1 g-extra cut, written as κ˜gG, is now obtained as the minimum cardinality above all g-extra cuts of G, namely, κ˜gG=κG;pg, whereat pg is the feature that each residual element takes at least g+1 nodes. Obviously, κ˜0G=κG for each linked incomplete graph G. Therefore, the traditional connectivity may be regarded as a simplification of g-extra connectivity, and it is able to serve for more precisely measuring the consistency and error lenience for INs. The g-extra connectivity of numerous INs was widely investigated (see [2–17]).It is worthwhile to mention that the algebraic connectivity [18] is another important metric in measuring how fine a graph is linked and is very significant in controller theory, communications, etc. Further research relating to algebraic connectivity are described in references [19, 20].Then-dimensional wheel network, a promising topology arrangement of INs, has some respectable things. Here, we establish that the g-extra connectivity of CWnn≥6 is 6n−12, when g=2.


## 2. Preliminaries

Definitions and notations used through this paper are provided. Then-dimensional wheel network and its basic properties are examined. We consider [21] for terms and notations not introduced in this paper.


### 2.1. Definitions and Notations

Consider a basic undirected graphG=V,E. Given U⊆V, U≠∅, the prompted graph determined by U in G, written as GU, is a graph in which set of nodes is U and the set of edges contains all the edges of G having both endpoints in U. For x∈V, the degree x in G is defined as the amount of edges neighboring to x, written as dGx. Let the minimum degree δG=mindGx:x∈V in G. For arbitrary node x∈V, the neighborhood NGx of x is determined as the set of nodes neighboring to x in a graph G. The node y is named a neighbor node of x, where y∈NGx. For U⊆V, NGU is applied to represent ∪x∈UNGx\U. If no confusion arises, then NGx, δG, and dGx can be abbreviated into Nx, δ, and dx, correspondingly. The set F containing all error nodes of G is named as a faulty set in G. Each node in F is named faulty and any node in VG\F is named faulty-free.


### 2.2. The Wheel Networks

The wheel networks have been known as a desirable topology structure of INs. Here, we recall its definition and some important aspects.ConsiderD to be a bounded group, Z to be a spanning set of D, where the identity element of D cannot be in Z. The linked Cayley graph CayZ,D has a set of nodes D and a set of arcs d,dz:d∈D,z∈Z. The condition that Z is a spanning set of D ensures that CayZ,D is linked. The assumption that the identity element of D cannot be in Z guarantees that CayZ,D is simple. For convenience, let n=1,2,…,n. Here, we concentrate on the Cayley graphs produced by transpositions. We choose the symmetric group Sn on n as D, and a set of transpositions of Sn as Z. Notice that Z contains only transposition, and there exists an arc x,y iff there exists an arc y,x, where xandy are two nodes. Thus, the corresponding Cayley graph can be viewed as an undirected Cayley graph.Consider a basic linked graphH whose set of nodes is nn≥3. Each edge of H is viewed as a transposition of the symmetric graph Sn on n; hence, the set of all edges of H resembles a transposition set Z of Sn. Therefore, H is entitled a transposition basic graph, and the resulting Cayley graph is said to be the corresponding Cayley graph of H, written as CayH,D. Akers et al. [22] proved that D=Sn in CayH,D.IfH mentioned above is a tree (resp. a path, a star), then the resulting Cayley graph is named a transposition tree (resp. a bubble-sort graph, a star graph) [22], written as CΓn (resp. Bn, Sn). When H is a sector SEn of nn≥3 nodes, i.e., VSEn=n and ESEn=1,k:2≤k≤n∪k,k+1:2≤k≤n−1, the resulting Cayley graph is named a bubble-sort star graph [23], written as BSn. If H is a wheel Wn of nn≥4 nodes, i.e., VWn=n and EWn=1,k:2≤k≤n∪k,k+1:2≤k≤n−1∪2,n, then the resulting Cayley graph is named a n-dimensional wheel network [24], written as CWn. In other words, CWn represents a graph with set of nodes VCWn = Sn, where 2 nodes xandy are neighboring iff x=y1,k, 2≤k≤n, or x=yk,k+1, 2≤k≤n−1, or x=y2,n. Figure 1 illustrates the Cayley graph CW4.Figure 1
The wheel network CW4.To discuss conveniently, we denote bya1a2⋯an the permutation 12…na1a2…an, where k⟶ak.Theorem 1.
(see [25]). Each permutation different from identity within the symmetric group is the only (considering the order of the factors) multiply of cycles that are not joined, where every cycle has length greater or equal to 2.Theorem 2.
(see [26]). Suppose that H is a basic linked graph where n=VH≥3, and H1 and H2 are a pair of diverse graphs gained by labelling H with n. Then, CayH1,Sn must be isomorphic to CayH2,Sn.
By Theorem1, each permutation must be written as a multiplication of cycles. For instance, 123231=123. In particular, 12…n12…n=1. The product η1η2 of 2 permutations η1 and η2 is the composition function η2 trailed by η1, i.e., 1323=132. For terms and notations not mentioned here we follow [25].
As a special Cayley graph,CWn owns many attractive properties.Proposition 1.
(see [27]). CWn is 2n−2-regular, node transitive, ∀n≥4.Proposition 2.
(see [27]). CWn is bipartite, ∀n≥4.Proposition 3.
(see [28]). The girth of CWn is 4, ∀n≥4.
In the next discussion, we often partitionCWninto n disjoint subgraphs CWn1,CWn2,\\…,CWnn, where each node x=x1x2…xn∈VCWnktakes a specified integer k in the latter place xn for k∈n. Evidently, each CWnkis isomorphic to BSn−1, where BSnis the bubble-sort star graph. For each node, x∈VCWnk, x1n, xn−1,n, and x2nare all named external neighbors of x, written as x+=x1n, x−=xn−1,n, and x∗=x2n, respectively. Any edge is named a cross-edge respectful to a fixed factorization if its 2 nodes are in diverse CWnk’s.Proposition 4.
(see [28]). Let x∈VCWnkk=1,2,…,n, where CWnk is mentioned as previously. Then, x+, x−, and x∗ are in three diverse CWnl’s l≠k.Proposition 5.
(see [29]). For x,y∈VCWnk, then x+,x−,x∗∩y+,y−,y∗=∅, where k∈n.Proposition 6.
(see [28]). Let CWnk be denoted as previously. There exist exactly 3n−2! autonomous cross-edges among 2 diverse CWnk’s.Theorem 3 (see [28]).
LetCWn be denoted as previously. If 2 nodes xandy are neighboring, no shared neighboring nodes exist of those nodes, that is, Nx∩Ny=0. If node x is not neighboring to y, maximally 3 mutual neighboring nodes exist of these nodes, namely, Nx∩Ny≤3.


## 2.1. Definitions and Notations

Consider a basic undirected graphG=V,E. Given U⊆V, U≠∅, the prompted graph determined by U in G, written as GU, is a graph in which set of nodes is U and the set of edges contains all the edges of G having both endpoints in U. For x∈V, the degree x in G is defined as the amount of edges neighboring to x, written as dGx. Let the minimum degree δG=mindGx:x∈V in G. For arbitrary node x∈V, the neighborhood NGx of x is determined as the set of nodes neighboring to x in a graph G. The node y is named a neighbor node of x, where y∈NGx. For U⊆V, NGU is applied to represent ∪x∈UNGx\U. If no confusion arises, then NGx, δG, and dGx can be abbreviated into Nx, δ, and dx, correspondingly. The set F containing all error nodes of G is named as a faulty set in G. Each node in F is named faulty and any node in VG\F is named faulty-free.


## 2.2. The Wheel Networks

The wheel networks have been known as a desirable topology structure of INs. Here, we recall its definition and some important aspects.ConsiderD to be a bounded group, Z to be a spanning set of D, where the identity element of D cannot be in Z. The linked Cayley graph CayZ,D has a set of nodes D and a set of arcs d,dz:d∈D,z∈Z. The condition that Z is a spanning set of D ensures that CayZ,D is linked. The assumption that the identity element of D cannot be in Z guarantees that CayZ,D is simple. For convenience, let n=1,2,…,n. Here, we concentrate on the Cayley graphs produced by transpositions. We choose the symmetric group Sn on n as D, and a set of transpositions of Sn as Z. Notice that Z contains only transposition, and there exists an arc x,y iff there exists an arc y,x, where xandy are two nodes. Thus, the corresponding Cayley graph can be viewed as an undirected Cayley graph.Consider a basic linked graphH whose set of nodes is nn≥3. Each edge of H is viewed as a transposition of the symmetric graph Sn on n; hence, the set of all edges of H resembles a transposition set Z of Sn. Therefore, H is entitled a transposition basic graph, and the resulting Cayley graph is said to be the corresponding Cayley graph of H, written as CayH,D. Akers et al. [22] proved that D=Sn in CayH,D.IfH mentioned above is a tree (resp. a path, a star), then the resulting Cayley graph is named a transposition tree (resp. a bubble-sort graph, a star graph) [22], written as CΓn (resp. Bn, Sn). When H is a sector SEn of nn≥3 nodes, i.e., VSEn=n and ESEn=1,k:2≤k≤n∪k,k+1:2≤k≤n−1, the resulting Cayley graph is named a bubble-sort star graph [23], written as BSn. If H is a wheel Wn of nn≥4 nodes, i.e., VWn=n and EWn=1,k:2≤k≤n∪k,k+1:2≤k≤n−1∪2,n, then the resulting Cayley graph is named a n-dimensional wheel network [24], written as CWn. In other words, CWn represents a graph with set of nodes VCWn = Sn, where 2 nodes xandy are neighboring iff x=y1,k, 2≤k≤n, or x=yk,k+1, 2≤k≤n−1, or x=y2,n. Figure 1 illustrates the Cayley graph CW4.Figure 1
The wheel network CW4.To discuss conveniently, we denote bya1a2⋯an the permutation 12…na1a2…an, where k⟶ak.Theorem 1.
(see [25]). Each permutation different from identity within the symmetric group is the only (considering the order of the factors) multiply of cycles that are not joined, where every cycle has length greater or equal to 2.Theorem 2.
(see [26]). Suppose that H is a basic linked graph where n=VH≥3, and H1 and H2 are a pair of diverse graphs gained by labelling H with n. Then, CayH1,Sn must be isomorphic to CayH2,Sn.
By Theorem1, each permutation must be written as a multiplication of cycles. For instance, 123231=123. In particular, 12…n12…n=1. The product η1η2 of 2 permutations η1 and η2 is the composition function η2 trailed by η1, i.e., 1323=132. For terms and notations not mentioned here we follow [25].
As a special Cayley graph,CWn owns many attractive properties.Proposition 1.
(see [27]). CWn is 2n−2-regular, node transitive, ∀n≥4.Proposition 2.
(see [27]). CWn is bipartite, ∀n≥4.Proposition 3.
(see [28]). The girth of CWn is 4, ∀n≥4.
In the next discussion, we often partitionCWninto n disjoint subgraphs CWn1,CWn2,\\…,CWnn, where each node x=x1x2…xn∈VCWnktakes a specified integer k in the latter place xn for k∈n. Evidently, each CWnkis isomorphic to BSn−1, where BSnis the bubble-sort star graph. For each node, x∈VCWnk, x1n, xn−1,n, and x2nare all named external neighbors of x, written as x+=x1n, x−=xn−1,n, and x∗=x2n, respectively. Any edge is named a cross-edge respectful to a fixed factorization if its 2 nodes are in diverse CWnk’s.Proposition 4.
(see [28]). Let x∈VCWnkk=1,2,…,n, where CWnk is mentioned as previously. Then, x+, x−, and x∗ are in three diverse CWnl’s l≠k.Proposition 5.
(see [29]). For x,y∈VCWnk, then x+,x−,x∗∩y+,y−,y∗=∅, where k∈n.Proposition 6.
(see [28]). Let CWnk be denoted as previously. There exist exactly 3n−2! autonomous cross-edges among 2 diverse CWnk’s.Theorem 3 (see [28]).
LetCWn be denoted as previously. If 2 nodes xandy are neighboring, no shared neighboring nodes exist of those nodes, that is, Nx∩Ny=0. If node x is not neighboring to y, maximally 3 mutual neighboring nodes exist of these nodes, namely, Nx∩Ny≤3.


## 3.κ˜ (2)(CWn)

Here, we establishκ˜2CWn=6n−12.Proposition 7.
(see [30]). Suppose that BSn is denoted as previously. Thus, BSn is 2n−3-regular, node transitive, ∀n≥2.Proposition 8.
(see [30]). Suppose that BSn is denoted as previously. The connectivity κBSn=2n−3, ∀n≥4.Lemma 1.
(see [30]). For n greater or equal to 4 and F is a subset of VBSn, where F≤4n−9. When BSn−F is detached, a single of these situations for BSn−F is valid:(1)
BSn−F has 2 constituents, with 1 isolated node(2)
BSn−F has 3 constituents, with 2 isolated nodesCorollary 1.
(see [29]). For n greater or equal to 4 and F is a subset of VBSn, where F≤4n−9. When BSn−F has 3 components, with 2 isolated nodes, it is valid that F≤4n−9.Lemma 2.
The 2-extra connectivityκ˜2CWn≤6n−12n≥5.Proof.
Observen≥5 and Z=12,13,…,1n,23,34,…,n−1,n∪2n. From Theorem 2, assume that A=1,12,123. It is valid: N1∩N123=12,13,23, N1∩N123\A=2. From Proposition 2, CWn contains none of 3-cycles. Applying it and Theorem 3, it is valid that NCWnA=6n−12. Consider F1=NCWnA and F2=NCWnA∪A, and CWn−F1 has two parts CWn−F2 and CWnA (see Figure 2).Figure 2
A depiction regarding the demonstrations of Lemma2 and Lemma 3.Let us now prove thatCWn−F2 is linked and δCWn−F2≥2.We factorizeCWn lengthways the latter location, written as CWnkk=1,…,n. Recall that each CWnk and BSn−1 are isomorphic for k∈n. Hence, CWnk is 2n−5-regular using Proposition 7, and κCWnk=2n−5 by Proposition 8 for each k∈n.Notice thatA⊆VCWnn, and NA∩VCWn1=2, NA∩VCWn2=3, NA∩VCWn3=1, NA∩VCWn4=⋯=NA∩VCWnn−2=0, and NA∩VCWnn−1=3. Using Proposition 6 and κCWnk=2n−5, CWn∪k=1n−1VCWnk−F1 is linked. Using Proposition 5, every node of CWnn−F2 is neighboring to 3 faulty-free nodes of CWn∪k=1n−1VCWnk−F1, and CWn∪k=1n−1VCWnk−F1∪VCWnn−F2 is linked. Combining NA∩VCWnk≤3 and κCWnk=2n−5, hence δCWnk−F2≥2, where k∈1,2,…,n−1 and n≥5. Therefore, CWn−F2 is linked and δCWn−F2≥2. Consequently, VCWn−F2≥3. CWn−F1 has 2 constituents: CWn−F2 and CWnA. Notice that VCWnA=3 is valid. Hence, F1 is really a 2-extra cut and κ˜2CWn≤6n−12.According to Lemma2, the next lemma is formulated.Lemma 3.
LetA=1,12,123. For n greater or equal to 5, F1=NCWnA,F2=NCWnA∪A, now F1=6n−12andF2=6n−9, F1 is a 2-extra cut of CWn, and CWn−F1 must have 2 constituents: CWn−F2 and CWnA (see Figure 2).Lemma 4.
For any integern≥6, κ˜2CWn≥6n−12.Proof.
ConsiderF to be a minimum 2-extra cut, and suppose F≤6n−13. We shall obtain a contradiction. Assume Fk=F∩CWnk. Observe 2 situations.Situation 1.
F
k
≤
2
n
−
6 for all k.
Notice thatκCWnk=2n−5; hence, CWnk−Fk is linked for each k. Using Proposition 6 and 2n−2!−Fk−Fl≥2n−2!−22n−6>0 for n≥6, we have that there must exist at least one edge to connect CWnk and CWnl, where k,l∈n and k≠l. Therefore, CWn−F is linked, which contradicts the assumption that F is a minimum 2-extra cut.Situation 2.
F
k
≥
2
n
−
5 for some k.
AssumeK=kFk≥2n−5. Recall that F≤6n−13, then we have K≤3. For any l∉K, Fl≤2n−6. From an analogous statement as in Situation 1, it is valid that ∪l∉KCWnl−Fl is linked, denoted it by B˜.Situation 2.1.
K
=
1.
In general, supposeK=1. Let C is a liked element of CWn1−F1. When VC≤2, C must be linked to B˜, since F is a 2-extra cut. If VC≥3, then C has a path P of three nodes. Suppose N1=NCWn1P∩F1 and N2=NCWn1P−N1∪VP. Thus, N1⊆F1 and N2⊆VC (see Figure 3.). Combining Theorem3 and CWnk is 2n−5-regular, NCWn1P≥32n−5−4−2=6n−21. By Propositions 4 and 5, N∪l∉KCWnlN2=3N2=3NCWn1P−N1+3VP≥NCWn1P−N1+3VP≥6n−21−F1+3×3=6n−12−F1>F−F1. Then, there must exist at least one node x∈C which has an external neighbor x′∈B˜; thus, C is linked to B˜. Using the randomness of C, CWn−F is linked, which contradicts that F is a minimum 2-extra cut.Figure 3
A diagram about the demonstration ofSituation 2.1 of Lemma 4.Situation 2.2.
K
=
2.
In general, suppose thatK=1,2 and C is a linked element of CWn1∪CWn2−F1−F2. When VC≤2, C must be linked to B˜, since F is an 2-extra cut. If VC≥3, then C has a path P of 3 nodes.
First, suppose that one ofCWn1−F1 and CWn2−F2, say CWn1−F1, has a path P on 3 nodes of C. Let N1=NCWn1P∩F1 and N2=NCWn1P−N1∪VP. Then, N1⊆F1, N2⊆VC, and F−F1−F2≤6n−13−2n−5−F1≤4n−8−F1. When n≥6, NCWn1P≥32n−5−4−2=6n−21. By Propositions 4and 5, N∪l∉KCWnlN2≥N2=NCWn1P−N1+VP≥6n−21−F1+3=6n−18−F1>4n−8−F1≥F−F1−F2 for n≥6. Then, there must exist at least one node x∈C which has an external neighbor x′∈B˜, and C is linked to B˜. From the randomness of C, CWn−F is linked, which contradicts that F is a minimum 2-extra cut.
If neitherCWn1−F1 nor CWn2−F2 has a path on three nodes of C, then any path P of CWn1−F1∪CWn2−F2 on three nodes has 2 nodes in a single side and 1 node in the different side, say P=y1y2y3 with y1,y2∈VCWn1−F1 and y3∈VCWn2−F2. Thus, NCWn1y1,y2⊆F1, F1≥NCWn1y1,y2=22n−5−2=4n−12 from Proposition 2, ∑l=3nFl=F−F1−F2≤6n−13−4n−12−2n−5=4. By Propositions 4 and 5, we see that N∪l∉KCWnlP≥6>∑l=3nFl; hence, P is linked to B˜; thus, C is also linked to B˜.
In any situations, we have shown thatCWn−F is linked, which contradicts the assumption that F is a minimum 2-extra cut.Situation 2.3.
K
=
3.
In general, supposeK=1,2,3. Since F≤6n−13 and Fk≥2n−5 for each k∈K, we have that 2n−5≤Fk≤2n−3, for k=1,2,3, and ∑k=4nFk≤2. Notice that 2n−3<4n−13 for n≥6, combining each CWnk is isomorphic to BSn−1 and Lemma 1 and Corollary 1; we have that, for each k∈K, if CWnk−Fk is disconnected, then CWnk−Fk has exactly 2 constituents, one of which is an inaccessible node which is written by yk. Notice that ∑l=4nFl≤2 and n≥6; hence, there must exist some CWnl which does not contain any faulty node. By Proposition 6 and 3n−2!>2n−3+1+0≥Fk+Fl, CWnk−Fk−yk and CWnl are linked for each k∈K. Hence, we have that ∪k=13CWnk−Fk−yk∪B˜which is written as B^ is linked. Next, we merely need to consider the situation that CWn−F is disconnected. Let CWn−F be disconnected and C be an arbitrary linked component. If VC≤2, then C is linked to B^ since F is a 2-extra cut; thus, y1,y2,andy3 must form a path, and the path is the only other linked component of CWn−F different from B^. Using Propositions 2, 4, and 5, then y1,y2,andy3 does not form a 3-cycle, and each of y1,y2, and y3 must have an external neighbor in ∪l=4nCWnl. Notice that ∑l=4nFl≤2; thus, there must exist at least one node yk which has an external neighbor yk′∈B˜; hence, it is shown that CWn−F is linked, which contradicts the assumption that F is a minimum 2-extra cut.
By Situations 1 and 2,F must be not a 2-extra cut of CWn and therefore F≥6n−12. Hence, κ˜2CWn≥6n−12 for n≥6.
According to obtained Lemmas2 and 4, the next is valid.Theorem 4.
κ
˜
2
CW
n
=
6
n
−
12
,
∀
n
≥
6
.


## 4. Conclusion

The traditional connectivity may be regarded as a simplification of theg-extra connectivity. It is gained that κ˜2CWn=6n−12n≥6. Notice that κ0CWn=κCWn=2n−2 when n≥4 and κ˜1CWn=4n−6, When n≥5 are obtained in [9]. We conclude the paper by summarizing which situations of g-extra connectivity of CWn have been not solved in Table 1.Table 1
Some situations ofg-extra connectivity of CWn continue.
g
/
n
4
5
n
≥
6
0
4
6
2
n
−
4
1
?
14
4
n
−
6
2
?
?
6
n
−
12
g
≥
3
?
?
?



---

*Source: 8910240-2020-04-28.xml*