# The Generalized 4-Connectivity of Cube-Connected-Cycle and Hierarchical Hypercube

Authors: Jinyu Zou; He Li; Haizhen Ren
Journal: Journal of Mathematics
 (2022)

---

## Abstract

The connectivity is an important measurement for the fault tolerance of a network. LetG=VG,EG be a connected graph with the vertex set VG and edge set EG. An S-tree of graph G is a tree T that contains all the vertices in S subject to S⊆VG. Two S-trees T and T′ are internally disjoint if and only if ET∩ET′=∅ and VT∩VT′=S. Denote κGS by the maximum number of internally disjoint S-trees in graph G. The generalized k-connectivity is a natural generalization of the classical connectivity, which is defined as κrG=minκGS|S⊆VGandS=r. In this paper, we mainly focus on the generalized connectivity of cube-connected-cycle CCCn and hierarchical hypercube HHCn, which were introduced for massively parallel systems. We show that for n=2m+2m≥1, κ4HHCn=m and κ4CCCn=2, that is, for any four vertices in CCCn (or HHCn), there exist 2 (or m) internally disjoint S-trees connecting them in CCCn (or HHCn).


---

## Body

## 1. Introduction

With the emergence and rapid development of high-performance parallel computer technology, people pay more and more attention to the interconnection network of good performance. The excellent topological structure has great advantages in improving reliability. In the design of the network topological structure, fault tolerance is the fundamental consideration, which implies that interconnection network can operate effectively when some nodes and edges fail, that is, it is able to retain some special properties of network. Moreover, the topological structure of an interconnection network can be modeled as an undirected graphG=V,E, where every vertex of V corresponds to a processor, and each edge of E corresponds to a communication link. Then, many computer scientists and engineers used some parameters of graph theory to design and analyze topological structures of interconnection networks, such as the connectivity.The connectivity of a graph is an essential parameter to measure the fault tolerance of an interconnection network. In general, the larger the connectivity of a graph is, the better the fault tolerance is. LetS∈VG; if the resulting graph by deleting S is disconnected or a trivial graph, S is called the cut set. The minimum cardinality of all cut sets of G is the connectivity of it, which is denoted as κG. There is another equivalent definition of the connectivity in [1]. For any vertex set S=u,v, κGS represents the maximum number of internally disjoint paths joining u and v in G, and κG=minκGS|S⊆VGandS=2. However, the connectivity has one drawback. As the event of vertex failure is random in real multiprocessor networks, it is almost unlikely that all vertices adjacent to the same vertices could fail simultaneously. In order to evaluate the fault tolerance of an interconnection network better, the researchers proposed some generalizations of classical connectivity, for example, the generalized k-connectivity, which was introduced in [2].AnS-tree of graph G is a tree T=V′,E′ that contains all the vertices of S subject to S⊆VG. Two S-trees T and T′ are internally disjoint if and only if ET∩ET′=∅ and VT∩VT′=S. Let κGS denote the maximum number of internally disjoint S-trees connecting S in G. For an integer k with 2≤k≤n, the generalized k-connectivity of a graph G is defined as κkG=minκGS|S⊆VGandS=k, which can evaluate the reliability of networks connecting any k vertices of G. Thus, the generalized 2-connectivity κ2G of G is exactly the connectivity κG, namely, κ2G=κG.Many researchers are interested in the generalizedk-connectivity and obtained some results. For a general graph G, Li and Li [3] showed that it is NP-complete to decide whether there are r internally disjoint trees connecting S, where r is a fixed integer and S⊆VG. In addition, the upper and lower bounds of the generalized connectivity were obtained in [4, 5]. For some popular networks, the results on the generalized 3-connectivity of them were given (see [6–11]). However, there are few results on generalized 4-connectivity (see [12, 13]). It is of great significance to study the generalized 4-connectivity. In this paper, we obtain the result of generalized 4-connectivity of cube-connected-cycle CCCn and hierarchical hypercube HHCn, which are important interconnection networks formed by replacing each vertex of hypercube as a cycle and a hypercube, respectively.The rest of this paper is organized as follows. In Section2, we introduce some notations and lemmas used in our proof. In Section 3, we determine the generalized 4-connectivity and generalized 3-connectivity of cube-connected-cycle. In Section 4, we give the generalized 4-connectivity and generalized 3-connectivity. In Section 5, we conclude this paper.


## 2. Notations and Preliminaries

LetG=V,E be a simple, undirected graph, and VG and EG are denoted as the order and size of G, respectively. For a vertex set V∈VG, GV is the subgraph of G induced by V. For a vertex v, the set of neighbors of v in a graph G is denoted by NGv. Let X⊆VG∪EG, and we use G−X to denote the subgraph of G obtained by removing all the vertices in X as well as removing all the edges in X from G. If X=x, we may write G−x instead of G−x.LetVn be the set of binary sequence of length n, i.e., Vn=x1x2…xn:xi∈0,1,1≤i≤n. For x=x1x2…xn∈Vn, the element x¯=x¯1x¯2…x¯n∈Vn is called the bitwise complement of x, where x¯i=0,1/xi for each i∈1,2,…,n. For an integer 1≤i≤n, xi=x1…xi−1x¯ixi+1…xn, PMi=x,xi|x∈VQn.Then-dimensional hypercube network Qn is a cube, shortly n-cube, with its vertex set Vn, and two vertices are adjacent if and only if they differ exactly in one coordinate. Figure 1 shows Q3. Clearly, PMi1≤i≤n is perfect matching of Qn, and EQn=∪i=1nPMi. Qn−1i0 and Qn−1i11≤i≤n are two n−1-cubes induced by vertices with the ith bit 0 and 1 of Qn, respectively, and then Qn can be denoted as Qn=Qn−1i0⊙PMiQn−1i11≤i≤n, where the symbol ⊙ represents the perfect matching operation that connects two different n−1-cubes.Figure 1
The 3-dimensional hypercubeQ3.For any1≤i,j≤n and i≠j, Qn−2i0,j0 and Qn−2i0,j1 are two n−2-cubes induced by the vertices with the jth bit 0 and 1 of Qn−1i0, respectively. Similarly, Qn−2i1,j0 and Qn−2i1,j1 are two n−2-cubes induced by the vertices with the jth bit 0 and 1 of Qn−1i1, respectively. Hence, Qn−1i0=Qn−2i0,j0⊙PMjQn−2i0,j1, Qn−1i1=Qn−2i1,j0⊙PMjQn−2i1,j1.By the structure ofQn, the following fact can be obtained easily.Fact 1.
For any two vertices ofQn, say u,v, if dQnu,v≤n−1, there exists i such that u,v∈VQn−1i0 or u,v∈VQn−1i1 for i∈1,2,…,n.
ForQn, the results on the connectivity are obtained in the book [14].Lemma 1.
κQn=n for n≥2.The generalized 4-connectivity ofQn is shown in [12].Lemma 2 (see [12]).
The generalized 4-connectivity of hypercubeQn is n−1, where n≥2.For anr-regular graph, the relation between the generalized k-connectivity and k−1-connectivity is investigated in [12].Lemma 3 (see [12]).
LetG be an r-regular graph. If κkG=r−1, then κk−1G=r−1, where k≥4.By Lemmas2 and 3, we obtain that κ3Qn=n−1 where n≥2.The upper bound of generalizedk-connectivity obtained by δG is given in [5].Lemma 4 (see [5]).
If there are two adjacent vertices of degreeδG, then κkG≤δ−1 for 3≤k≤VG.For anyU⊆VG and V⊆VG∖U, U,V-paths denote a set of internally disjoint paths, two endpoints of each path are u∈U and v∈V, respectively, and the internal vertices belong neither to U nor V. If U=u, V=v1,v2,…,vk, then U,V-path is a family of k internally disjoint paths joining u and v1,v2,…,vk, which is referred to as a k-fan from u to V.Lemma 5 (see [14]).
LetG be a graph with κG=k, x∈VG, Y⊆VG∖x, and Y≥k. Then, there exists a k-fan in G from x to Y. That is, there exists a family of k internally vertex disjoint x,Y-paths whose terminal vertices are distinct in Y.


## 3. The Generalized 4-Connectivity ofCCCn

The graph cube-connected-cycleCCCn [15] has n×2n vertices labeled as ℓ,x, where ℓ is an integer between 0 and n−1, called the level of the vertex, and x is a binary string of length n, called the row of x. All arithmetic on indices and levels concerning CCCn is assumed to be modulo n. Two vertices ℓ,x and ℓ′,x are adjacent if and only if either x=y and ℓ−ℓ′=1 or ℓ=ℓ′ and x=ℓy. The latter case means that x and y differ in exactly the bit in position ℓ.CCCn is formed by replacing each vertex of a hypercube graph Qn by a cycle of length n. Furthermore, from the definition, one can easily check that all the triangles (resp. quadrangles and pentagons) in CCC3 (resp. CCC4 and CCC5) are exactly those cycles replaced on each vertex in Q3resp.Q4,Q5 in the procedure of creating CCCn from Qn for n=3,4 and 5. Figure 2 shows CCC3.Figure 2
The 3-dimensional cube-connected-cycleCCC3.LetVQn=x1,x2,…,x2nn≥4, x1Cn,x2Cn,…,x2nCn be 2n cycles of length of n in CCCn. Suppose that u,u′∈VCCCn, and u∈VxiCn,u′∈VxjCn for 1≤i≠j≤n; if u is adjacent to u', then, u′ is denoted by the external neighbor of u.Theorem 1.
Forn≥4, κ4CCCn=2.Proof.
Leta,b,c,d be any four vertices of CCCn. In order to complete the proof, we consider the following cases.Case 1. a,b,c,d are distributed in the same cycle.Without loss of generality, we suppose thata,b,c,d∈Vx1Cn. As x1Cn is connected, there is a tree T1 connecting a,b,c, and d in x1Cn. Denote a′,b′,c′,d′ as the external neighbors of a,b,c,d, respectively. Moreover, CCCn−x1Cn is connected; then, there is a tree connecting a′,b′,c′, and d′, say T2′, T2=T2′∪a,a′∪b,b′∪c,c′∪d,d′. Hence, T1,T2 are the desired trees.Case 2. a,b,c,d are distributed in two different cycles.Subcase 2.1. Three vertices of a,b,c,d are in one cycle, and the remaining vertex of a,b,c,d is in other cycle.Without loss of generality, supposea,b,c∈Vx1Cn, d∈Vx2Cn. By Lemma 1, κQn=n, so there are n internally disjoint paths joining x1 and x2, say P1,…,Pn. Denote NQnx1=x3,…,xn+2, NQnx2=xn+3,…,x2n+2; without loss of generality, suppose xi+2,xn+i+2∈VPi where 1≤i≤n. Let X=x3Cn,…,xn+2Cn, Y=xn+3Cn,…,x2n+2Cn, and X,Y-paths can be denoted as R1,…,Rn, where Ri is a path joining xi+2Cn and xn+i+2Cn for i∈1,…,n. As x1Cn is a cycle and n≥4, there is a tree T1′ connecting a,b,c such that T1′ has at least 4 vertices. Let f∈VT1′ and f≠a,b,c, and the external neighbor of it be f′, and f′ must be in some Vxi+2Cn for i∈1,…,n, say i=1. Suppose e∈Vx2Cn, e′ is the external neighbor of e, and e′∈Vxn+3Cn; clearly, there is a path joining e and d in x2Cn, say M1, so T1=T1′∪f,f′∪R1∪e,e′∪M1. Denote the external neighbor of a,b,c,d by a′,b′,c′,d′, a′∈Vx4Cn, b′∈Vx5Cn, c′∈Vx6Cn, d′∈Vxn+4Cn. As Qn−P1 is connected, CCCn−T1 is also connected, and there is a tree connecting a′,b′,c′,d′, say T2′, T2=T2′∪a,a′∪b,b′∪c,c′∪d,d′; then, T1,T2 are the desired trees (see Figure 3). If d′∈Vxn+3Cn, we can suppose that e′∈Vxn+4Cn, and two desired paths can be found similarly.Subcase 2.2. Two vertices of a,b,c,d are in one cycle, and the remaining two vertices of a,b,c,d are in other cycle.Without loss of generality, supposea,b∈Vx1Cn, c,d∈Vx2Cn. The proof is similar to Subcase 2.1. There are two internally disjoint paths joining a and b in x1Cn, say P1′,P2′, and there is a Pi′i=1,2 containing at least three vertices, say P1′. Suppose f∈VP1′, and f≠a,b, and the external neighbor of f is in x3Cn, say f′. As x2Cn is connected, there is a tree connecting e,c,d, say M1; then, T1=P1′∪f,f′∪R1∪e′,e∪M1. Let a′∈Vx4Cn, b′∈Vx5Cn, c′∈Vxn+4Cn, Vxn+5Cn. There is a tree T2′ connecting a′,b′,c′,d′, T2=T2′∪a,a′∪b,b′∪c,c′∪d,d′. Hence, T1,T2 are the desired trees (see Figure 4).Case 3. a,b,c,d are distributed in three different cycles.Without loss of generality, we suppose thata,b∈Vx1Cn, c∈Vx2Cn, d∈Vx3Cn. As κ3Qn=n−1 for n≥2, there are n−1 internally disjoint S-trees connecting x1,x2, and x3 in Qn, and each tree contains at least one neighbor of x1,x2, and x3. Then, there are n−1 internally disjoint trees connecting x1Cn,x2Cn, and x3Cn, say T1′,T2′,…,Tn−1′, and Ti′1≤i≤n−1 contains at least one vertex of xiCni=1,2,3. Also, xiCn=ni=1,2,3; there exists at most one vertex of xiCn not in VTj′1≤j≤n−1. There are 2 internally disjoint paths joining a and b in x1Cn, say P1′,P2′. We can claim that there is ii=1,2 such that VPi′≥3; without loss of generality, VP2′≥3. Hence, there are two vertices, e1 and e2, e1∈VP1′,e2∈VP2′ (e1,e2 can be a or b) such that e1∈VTi′, e2∈VTj′, where 1≤i≠j≤n−1, say i=1,j=2. Suppose c1,d1∈VT1′, c2,d2∈VT2′, c1,c2∈Vx2Cn, d1,d2∈Vx3Cn. There are two paths joining c and c1,c2, say M1,M2, respectively. Similarly, there are two paths joining d and d1,d2, say N1,N2, respectively. Let Ti=Pi′∪Ti′∪Mi∪Nii=1,2; then, T1,T2 are the desired trees (see Figure 5).Case 4. a,b,c,d are in four different cycles.
Without loss of generality, we supposea∈Vx1Cn, b∈Vx2Cn, c∈Vx3Cn, d∈Vx4Cn. By Lemma 2, κ4Qn=n−1, and there are n−1 internally disjoint trees connecting x1,x2,x3, and x4, and each tree contains at least one neighbor of xii=1,2,3,4. Then, there are n−1 trees connecting x1Cn,x2Cn,x3Cn, and x4Cn, say T1′,T2′,…,Tn−1′, and Ti′1≤i≤n−1 contains at least one vertex of xjCnj=1,2,3,4. For n≥4, there are two vertices, a1,a2∈Vx1Cn, such that a1∈VT1′, a2∈VT2′. Similarly, suppose b1,b2∈Vx2Cn, c1,c2∈Vx3Cn, d1,d2∈Vx4Cn, and b1,c1,d1∈VT1′, b2,c2,d2∈VT2′. There are two paths joining a and a1,a2, say M1 and M2. Similarly, there are two paths joining b and b1,b2, say N1 and N2, there are two paths joining c and c1,c2, say R1 and R2, and there are two paths joining d and d1,d2, say L1 and L2. Then, Ti=Ti′∪Mi∪Ni∪Ri∪Li where i=1,2, T1,T2 are the desired trees (see Figure 6), and the proof is complete.
From Lemma3 and Theorem 1, we can obtain the following corollary.Figure 3
The illustration of subcase 2.1 of Theorem1.Figure 4
The illustration of subcase 2.2 of Theorem1.Figure 5
The illustration of case 3 of Theorem1.Figure 6
The illustration of case 4 of Theorem1.Corollary 1.
Forn≥4, κ3CCCn=2.


## 4. The Generalized 4-Connectivity ofHHCn

The hierarchical hypercubeHHCn was proposed in [16], which is a modification of an n-dimension cube-connected-cycle CCCn [15], and the cycle is replaced with a hypercube. The definition and some available properties of hierarchical hypercube are introduced as follows.Definition 1.
(see [16]). The vertex set of n-dimensional hierarchical hypercube HHCn is denoted as X,Y|X=an−1an−2…am,Y=am−1am−2…a0, andai∈0,1forall0≤i≤n−1. For any vertex A,B of HHCn, the adjacency of it is defined as follows: A,B is adjacent to(1)
A,Bℓ for all 0≤ℓ≤m−1.(2)
Am+decB,B, where decB is the decimal value of B.
Ann-dimensional hierarchical hypercube HHCn is a m+1-regular bipartite graph of order 2n, where n=2m+m. HHCn is triangle-free and consists of 22m clusters, and each cluster is isomorphic to Qm. Let VQ2m=x1,x2,…,x22m, and x1Qm,x2Qm,…,x22mQm be the 22m clusters of HHCn. The cross edges between the clusters have the property that every node is incident to exactly one of them (i.e., perfect matching). Q22 is shown in Figure 7, and HHC6 with m=2 is shown in Figure 8.
By the definition of hypercube,Q2m=Q2m−1i0⊙PMi∪Q2m−1i11≤i≤2m. For any 1≤i,j≤2m and i≠j, Q2m−1i0=Q2m−2i0,j0⊙PMj∪Q2m−2i0,j1, Q2m−1i1=Q2m−2i1,j0⊙PMj∪Q2m−2i1,j1. Suppose that u,u′∈VHHCn, and u∈VxiQm,u′∈VxjQm for 1≤i≠j≤2m; if u is adjacent to u', then, u′ is denoted by the external neighbor of u.
In order to obtain the result onκ4HHCn, the following lemmas are needed.
AsQ2 is isomorphic to C4, for any three vertices a,b,c of Q2, there must be a path with 4 vertices connecting a,b,c.Figure 7
The hypercubeQ22.Figure 8
The 6-dimensional hierarchical hypercubeHHC6.Lemma 6.
Leta,b,c∈VQm,m≥2; there exist m−1 internally disjoint trees connecting a,b,c and each one contains at least 4 vertices.Proof.
It proceeds by induction onm. The result holds for m=2. Now we suppose that m≥3 and the lemma holds for m−1. Qm consists of two different Qm−1,s and perfect matching between them, Qm=Qm−1i0⊙PMiQm−1i1 where i∈1,2,…,m.
Whena,b,c are distributed in the same Qm−1, say a,b,c∈VQm−1i0, as κ3Qm−1i0=m−2, there are m−2 internally disjoint S-trees connecting a,b,c such that each tree has at least 4 vertices by induction hypothesis, say T1,…,Tm−2. Let a′,b′,c′ be the external neighbors of a,b,c in Qm−1i1, respectively; there is a tree connecting a′,b′,c′ in Qm−1i1, say R′. Let Tm−1=R′∪a,a′∪b,b′∪c,c′; then, T1,…,Tm−1 are the desired trees.
Whena,b,c are distributed in two Qm−1,s, there must be two vertices of a,b,c, say a,c, such that da,c=m by Fact 1. Without loss of generality, suppose a,b∈VQm−1i0, and c∈VQm−1i1. By Lemma 1, κQm−1i0=m−1, and there are m−1 internally disjoint paths joining a and b, say P1′,…,Pm−1′. If each Pi′i=1,…,m−1 contains at least 3 vertices, choose one vertex of Pi′, say vivi≠a,b and vi is adjacent to a. Denote vi′i=1,…,m−1 by the external neighbor of vi. By Lemma 5, there are m−1 paths joining c and v1′,v2′,…,vm−1′, say Lii=1,…,m−1, Ti=Li∪vi,vi′∪Pi′,i=1,…,m−1. If there is one path Pi′i=1,…,m−1 containing only two vertices, that means a is adjacent to b, say a=v1, and Pi′i=2,…,m−1 contains at least 3 vertices. Clearly, L1 contains at least 3 vertices, and hence T1 contains at least 5 vertices. Tii=2,…,m−1 can be obtained by the proof above.
By Lemma1, κQ2m=2m, and there are 2m internally disjoint paths joining x1 and x2, say P1,P2,…,P2m, NQ2mx1=v1,…,v2m, NQ2mx2=u1,…,u2m, and vi,ui∈VPi for each i∈1,2,…,2m.Lemma 7.
Form≥2, P1,P2,…,P2m are 2m internally disjoint paths joining x1 and x2 in Q2m, and P is denoted as the set consisting of any m−1 paths of P1,P2,…,P2m. Then, Q2m−P is connected.Proof.
We complete the proof by the value ofdQ2mx1,x2.
First we supposedQ2mx1,x2≤2m−1. By Fact 1, there is i such that x1,x2∈VQ2m−1i0 or x1,x2∈VQ2m−1i1 for i∈1,2,…,2m. Without loss of generality, suppose i=1 and x1,x2∈VQ2m−110. Let j=2, Q2m−110=Q2m−210,20⊙PM2∪Q2m−210,21, Q2m−111=Q2m−211,20⊙PM2∪Q2m−211,21. When m=2, the result can be proved easily. For example, Figure 9 shows the case that x1 and x2 are adjacent. Now we suppose m≥3 and the lemma holds for m−1, and P1,P2,…,P2m are shown in Figure 10. If P2m∈P, then there are m−2 paths of P1,P2,…,P2m−1 in P, say P1,P2,…,Pm−2. As 2m−1>2m−1 for m≥3, Q2m−110−P1∪P2∪⋯∪Pm−2 must be connected, and Q2m−111−P2m−x1,x2 is connected. For any vertex x∈VQ2m−210,20 not deleted, we can find its external neighbor x′ in Q2m−211,20, so Q2m−P is connected. If P2m∉P, that means P consists of m−1 paths of P1,P2,…,P2m−1, say P1,P2,…,Pm−1. So, for any vertex y∈VQ2m−110−P not deleted, we can find its external neighbor y′ of Q2m−111; then, Q2m−P is connected.
Next we supposedQ2mx1,x2=2m, and P1,P2,…,P2m are shown in Figure 11; v2m∈VQ2m−211,20. NQ2mx2=u1,…,u2m, and u1∈VQ2m−210,21, u2m∈VQ2m−211,20. Denote the external neighbor of vi and ui in Q2m−211,20 by vi′ and ui′, respectively, for i∈2,3,…,2m−1. Let R1,R2m be the paths joining v1 and u1, v2m and u2m, respectively, and Rii∈2,3,…,2m−1 be the path joining vi′ and ui′, VR1=VR2m=2m−1, VRi=2m−3i∈2,3,…,2m−1. Choose any m−1 paths of P2,…,P2m−1, say P2,…,Pm. Let P′=P1,P2,…,Pm,P2m. As Q2m−210,20−x1,v2,…,vm is connected, and Q2m−210,21−R1 is also connected. Also, x1,v2,…,vm=m,m<2m−1m≥3, and there is a vertex q∈VQ2m−210,21−R1 and its neighbor q′∈VQ2m−210,20−x1,v2,…,vm; then, Q2m−110−R1∪x1,v2,…,vm is connected. For any vertex m∈VQ2m−211,20−R2∪R3∪…∪Rm∪R2m, its external neighbor m′∈VQ2m−210,20−x1,v2,…,vm. Furthermore, Q2m−211,21−x2,u2,…,um must be connected. As x2,u2,…,um=m,m<2m−1m≥3, there is a vertex n∈VQ2m−211,21−x2,u2,…,um and its neighbor n′ is in Q2m−210,21−R1. Hence, Q2m−P′ is connected. Also, P can be obtained by deleting one path of P′, Q2m−P is also connected, and the proof is complete.Figure 9
Q22.Figure 10
The illustration ofdQ2mx1,x2≤2m−1 of Lemma 7.Figure 11
The illustration ofdQ2mx1,x2=2m of Lemma 7.Lemma 8.
Form≥2, the set formed by any m vertices of NQ2mx1 and NQ2mx2 is denoted as A and B, respectively. There are m internally disjoint paths between A and B.Proof.
It proceeds by induction onm. For m=2, without loss of generality, suppose A=v1,v2, B=u1,u2. As Q22 is connected, then there is a path joining v1 and uii=1,2, say u1, which is denoted as L1. By Lemma 7, Q22L1,x1,x2 is also connected; then, there is a path joining v2 and u2. So, L1,L2 are the desired paths joining A and B.
Now we suppose thatm≥3 and the result holds for m−1. We set A=v1,v2,…,vm, B=u1,u2,…,um, A′=v1,v2,…,vm−1, and B′=u1,u2,…,um−1. By induction hypothesis, there are m−1 internally disjoint paths joining A′ and B′, L1,…,Lm−1. By Lemma 7, Q2m−L1,…,Lm−1,x1,x2 is connected, so there is path joining vm and um, say Lm. The proof is completed.Theorem 2.
Letn,m be two integers with m≥2 and n=2m+m. Then, κ4HHCn=m.Proof.
Letx,y,z,w be any four vertices of HHCn. For completing the proof, we consider the following cases.Case 1. x,y,z,w are distributed in one cluster.Without loss of generality, we supposex,y,z,w⊆Vx1Qm. By Lemma 2, κ4x1Qm=m−1, and there are m−1 internally disjoint S-trees connecting x,y,z, and w, say T1,…,Tm−1. Let x′,y′,z′,w′ be the external neighbors of x,y,z,w, respectively, say x′∈Vx2Qm,y′∈Vx3Qm,z′∈Vx4Qm,′∈Vx5Qm. As HHCn−Vx1Qm is connected, there is a tree connecting x′,y′,z′, and w′, say Tm′, Tm=Tm′∪x,x′∪y,y′∪z,z′∪w,w′. Then, T1,…,Tm are the desired trees.Case 2. x,y,z,w are distributed in two clusters.Subcase 2.1. Three vertices of x,y,z,w are in one cluster, and the remaining one vertex of x,y,z,w is in another cluster.Without loss of generality, letx,y,z,⊆Vx1Qm, w∈Vx2Qm. By Lemma 6, there are m−1 internally disjoint trees connecting x,y,z such that each one has at least 4 vertices, say T1′,…,Tm−1′. Choose one vertex of each Ti′ different from x,y, and z, say ai1≤i≤m−1. For any vertex of x1Qm, the external neighbor of it must be in some vjQm1≤j≤2m. Let the external neighbor of ai be ai′; without loss of generality, ai′∈VviQm for each i∈1,…,m−1. Let ci,ci′∈EHHCn, and ci∈Vx2Qm, ci′∈VuiQm, 1≤i≤m. As there are 2m internally disjoint paths joining x1 and x2 in Q2m, P1,…,P2m, there are 2m paths joining x1Qm and x2Qm. Clearly, there are m−1 internally disjoint paths between a1′,…,am−1′ and c1′,…,cm−1′, say Ri1≤i≤m−1. By Lemma 5, there are m paths joining w and c1,…,cm, say Ni1≤i≤m, Ti=Ri∪Ni∪ai,ai′∪ci,ci′∪Ti′1≤i≤m−1. By Lemma 7, the resulting graph by deleting m−1 paths of P1,…,P2m is connected; then, HHCn−R1∪…∪Rm−1∪c1Qm∪c2Qm is connected. Let x′,y′,z′,w′ be the external neighbor of x,y,z,w, respectively, and x′∈VvmQm, y′∈Vvm+1Qm, z′∈Vvm+2Qm, w∈Vvm+3Qm. There is a tree Tm′ connecting x,y,z, and w in HHCn−R1∪…∪Rm−1∪c1Qm∪c2Qm, Tm=Tm′∪x,x′∪y,y′∪z,z′∪w,w′. T1,…,Tm are the desired trees (see Figure 12).Subcase 2.2. Two nodes of x,y,z,w are in one cluster, and the remaining two vertices of x,y,z,w are in another cluster.Without loss of generality, we setx,y⊆Vx1Qm, z,w⊆Vx2Qm. By Lemma 1, κQm=m, and there are m internally disjoint paths joining x,y, say Mi1≤i≤m, and m internally disjoint paths joining z and w, say Ni1≤i≤m. Choose two vertices of Mi and Ni, say ai and bi, respectively. Let the external neighbor of ai be ai′, and ai′∈VviQm, and the external neighbor of bi be bi′, and bi′∈VuiQm where i∈1,2,…,m. By Lemma 8, there are m internally disjoint paths joining v1,…,vm and u1,…,um in Q2m. Hence, there are m paths joining a1′,…,am′ and b1′,…,bm′, say R1,…,Rm. Then, Ti=Mi∪ai,ai′∪Ri∪bi,bi′∪Ni for 1≤i≤m. T1,…,Tm are the desired trees, which are shown in Figure 13.Case 3. x,y,z,w are distributed in three clusters.Without loss of generality, we supposex,y⊆Vx1Qm, z∈Vx2Qm, w∈Vx3Qm. There are m internally disjoint paths joining x,y, say Mi1≤i≤m. For κ3Q2m=2m−1, there are 2m−1 internally disjoint S-trees connecting x1,x2 and x3, say T1′,T2′,…,T2m−1′. We set NQ2mx3=d1,…,dm. Without loss of generality, we suppose vi,ui,di∈VTi′ for each i∈1,2,…,2m−1. So, there must be 2m−1 internally disjoint trees connecting x1Qm,x2Qm and x3Qm, say R1,R2,…,R2m−1. Choose one vertex ai of Mi; then, ai1≤i≤m must be in some VRj1≤j≤2m−1. Without loss of generality, suppose ai∈VRi, zi,zi′∈ERi, wi,wi′∈ERi, and zi′∈VuiQm,wi′∈VdiQm, zi∈Vx2Qm,wi∈Vx3Qm for each i∈1,2,…,m. m paths between z and z1,…,zm are denoted by N1,…,Nm, and m paths between w and w1,…,wm are denoted by Q1,…,Qm. Then, Ti=Mi∪Ri∪Ni∪Qi for i∈1,2,…,m (see Figure 14).Case 4. x,y,z,w are distributed in four clusters.
Without loss of generality, we setx∈Vx1Qm, y∈Vx2Qm, z∈Vx3Qm, and w∈Vx4Qm. By κ4Q2m=2m−1, there are 2m−1 internally disjoint S-trees connecting x1,x2,x3, and x4, say T1′,…,T2m−1′. Let NQ2mx4=e1,…,e2m, vi,ui,di,ei∈VLi for i∈1,2,…,2m−1. Hence, there are 2m−1 internally disjoint trees connecting x1Qm, x2Qm, x3Qm, and x4Qm of HHCn, say L1,…,L2m−1. We set ai,ai′,yi,yi′,zi,zi′,wi,wi′∈ELi, ai′,yi′,zi′,wi′∈VLi, ai∈Vx1Qm,yi∈Vx2Qm,zi∈Vx3Qm,wi∈Vx4Qm for each i∈1,2,…,m. The m paths joining x and a1,…,am are denoted by M1,…,Mm, the m paths joining y and y1,…,ym are denoted by Y1,…,Ym, the m paths joining z and z1,…,zm are denoted by Z1,…,Zm, and the m paths joining w and w1,…,wm are denoted by W1,…,Wm. Then, Ti=Li∪Mi∪Yi∪Zi∪Wi for each i∈1,2,…,m (see Figure 15), and the proof is complete.
From Lemma3 and Theorem 2, the following corollary can be obtained easily.Figure 12
The illustration of subcase 2.1 of Theorem2.Figure 13
The illustration of subcase 2.2 of Theorem2.Figure 14
The illustration of case 3 of Theorem2.Figure 15
The illustration of case 4 of Theorem2.Corollary 2.
Letn,m be two integers with m≥2 and n=2m+m. Then, κ3HHCn=m.


## 5. Conclusions

The hypercubeQn is an important interconnection network. CCCn is formed by replacing each vertex of a hypercube Qn by a cycle of length n. The hierarchical hypercube is a modification of an n-dimension cube-connected-cycle, and the cycle is replaced with a hypercube. The generalized k-connectivity of interconnection network is a parameter to evaluate the reliability and fault tolerance of it. In this paper, we obtain the generalized 4-connectivity of cube-connected-cycle and hierarchical hypercube. In the future work, the generalized k-connectivity of the networks for k≥5 would be an interesting problem.



---

*Source: 2766404-2022-11-25.xml*