# Hamilton Paths and Cycles in Varietal Hypercube Networks with Mixed Faults

Authors: Jian-Guang Zhou; Jun-Ming Xu
Journal: International Journal of Combinatorics
 (2015)

---

## Abstract

This paper considers the varietal hypercube networkVQn with mixed faults and shows that VQn contains a fault-free Hamilton cycle provided faults do not exceed n-2 for n⩾2 and contains a fault-free Hamilton path between any pair of vertices provided faults do not exceed n-3 for n⩾3. The proof is based on an inductive construction.


---

## Body

## 1. Introduction

As a topology of interconnection networks, the hypercubeQn is the most simple and popular since it has many nice properties. The varietal hypercube VQn is a variant of Qn and proposed by Cheng and Chuang [1] in 1994 and has many properties similar or superior to Qn. For example, they have the same numbers of vertices and edges and the same connectivity and restricted connectivity (see Wang and Xu [2]), while all the diameter and the average distances, fault-diameter, and wide-diameter of VQn are smaller than those of the hypercube Qn (see Cheng and Chuang [1], Jiang et al. [3]). Recently, Xiao et al. [4] have shown that VQn is vertex-transitive.Embedding paths and cycles in various well-known networks, such as the hypercube and some well-known variations of the hypercube, have been extensively investigated in the literature (see, e.g., Tsai [5] for the hypercubes, Fu [6] for the folded hypercubes, Huang et al. [7] and Yang et al. [8] for the crossed cubes, Yang et al. [9] for the twisted cubes, Hsieh and Chang [10] for the Möbius cubes, Li et al. [11] for the star graphs and Xu and Ma [12] for a survey on this topic). Recently, Cao et al. [13] have shown that every edge of VQn is contained in cycles of every length from 4 to 2n except 5, and every pair of vertices with distance d is connected by paths of every length from d to 2n-1 except 2 and 4 if d=1, from which VQn contains a Hamilton cycle for n⩾2 and a Hamilton path between any pair of vertices for n⩾3. Huang and Xu [14] have improved this result by considering edge-faults and showing that VQn contains a fault-free Hamilton cycle provided faulty edges do not exceed n-2 for n⩾3 and a fault-free Hamilton path between any pair of vertices provided faulty edges do not exceed n-3 for n⩾3. In this paper, we will further improve these results by considering mixed faults of vertices and edges and proving that VQn contains a fault-free Hamilton cycle provided the number of mixed faults does not exceed n-2 for n⩾2 and contains a fault-free Hamilton path between any pair of vertices provided the number of mixed faults does not exceed n-3 for n⩾3.The proofs of these results are in Section3. The definition and some basic structural properties of VQn are given in Section 2.


## 2. Definitions and Structural Properties

We follow [15] for graph-theoretical terminology and notation not defined here. A graph G=(V,E) always means a simple and connected graph, where V=V(G) is the vertex-set and E=E(G) is the edge-set of G. For xy∈E(G), we call x (resp., y) a neighbor of y (resp., x).LetGk be a labeled graph with vertex set Vk={xk⋯x2x1:xi∈{0,1},1⩽i⩽k}. For j⩾1, let αj=yj⋯y1, where yi∈{0,1} for each i=1,…,j. Use Gkαj to denote a labeled graph obtained from Gk by inserting the string αj in front of each vertex-labeling in Gk. Clearly, Gkαj≅Gk.Definition 1.
Then-dimensional varietal hypercube VQn is the labeled graph defined recursively as follows. VQ1 is the complete graph of two vertices labeled with 0 and 1, respectively. Assume that VQn-1 has been constructed. For n>1, VQn=VQn-10⊙VQn-11 is obtained from VQn-10 and VQn-11 by joining vertices between them, according to the rule: a vertex x=0xn-1xn-2xn-3⋯x2x1 in VQn-10 and a vertex y=1yn-1yn-2yn-3⋯y2y1 in VQn-11 are adjacent in VQn if and only if(1)
xn-1xn-2xn-3⋯x2x1=yn-1yn-2yn-3⋯y2y1 if n≠3k, or(2)
xn-3⋯x2x1=yn-3⋯y2y1 and (xn-1xn-2,yn-1yn-2)∈I if n=3k, where I={(00,00),(01,01),(10,11),(11,10)}.Figure1 shows the examples of varietal hypercubes VQn for n=1,2,3, and 4, respectively.Figure 1
The varietal hypercubesVQ1, VQ2, VQ3, and VQ4.For convenience, we writeVQn=L⊙R, where L=VQn-10 and R=VQn-11. Clearly, the set M of edges between L and R is a perfect matching of size 2n-1 in VQn. Use xLxR to denote an edge in M joining xL∈L and xR∈R. By the recursive definition of VQn, VQn-10=VQn-200⊙VQn-201 and VQn-11=VQn-210⊙VQn-211. Thus, VQn is of the recursive structure shown as in Figure 2.Figure 2
The recursive structure ofVQn.
(a)
n
≠
3
k
(b)
n
=
3
kUseU and W to denote two subgraphs of VQn induced by V(VQn-200)∪V(VQn-210) and V(VQn-201)∪V(VQn-211), respectively. It should be noted that U and W are not always isomorphic to VQn-1, although L and R are isomorphic to VQn-1.Definition 2.
The graphGn=Gn-10⊕MGn-11 is the labeled graph defined recursively as follows. G1 is the complete graph of two vertices labeled with 0 and 1, respectively. G2=G10⊕G11 is obtained from G10 and G11 plus two edges joining 00 and 10, 01, and 11. For n⩾3, Gn=Gn-10⊕MGn-11 is obtained from Gn-10 and Gn-11 by adding a perfect matching M between Gn-10 and Gn-11, according to the following rule: M consists of two perfect matchings M1 and M2, where M1 is a perfect matching between Gn-200 and Gn-210 and M2 is a perfect matching between Gn-201 and Gn-211.Clearly, by Definition1, in VQi, the set M of edges between VQi-10 and VQi-11 is a perfect matching between them satisfying the rule in Definition 2. Thus, VQn is a special example of Gn. We state this fact as a simple observation.Observation 1.
For eachi=2,…,n, VQi≅VQi-10⊕MVQi-11 for the perfect matching M defined by the rule in Definition 1. Moreover, G3≅Q3 or VQ3, where Q3 is a 3-dimensional cube.


## 3. Main Results

LetG be a graph, and let x and y be two distinct vertices in G. A subgraph P of G is called an xy-path, if its vertex-set can be expressed as a sequence of adjacent vertices, written as P=(x0,x1,x2,…,xm), in which x=x0, y=xm, and all the vertices x0,x1,x2,…,xm are different from each other. For a path P=(x0,…,xi,xi+1,…,xm), we can write P=P(x0,xi)+xixi+1+P(xi+1,xm), and the notation P-xixi+1 denotes the subgraph obtained from P by deleting the edge xixi+1. If P is an xy-path and xy∈E(G), then P+xy is called a cycle in G. A cycle is called a Hamilton cycle if it contains all vertices in G. An xy-path P is called an xy-Hamilton path if it contains all vertices in G. A graph G is Hamiltonian if it contains a Hamilton cycle and is called Hamilton-connected if it contains an xy-Hamilton path for any two vertices x and y in G. Clearly, if G has at least three vertices and is Hamilton-connected, then it certainly is Hamiltonian; moreover, every edge is contained in a Hamilton cycle.Lemma 3 (Cao et al. [13]).
V
Q
n is Hamilton-connected for n⩾3, and so every edge of VQn is contained in a Hamilton cycle for n⩾2.LetF be a subset of V(G)∪E(G). A subgraph H of G is called fault-free if H contains no elements in F. A graph G is called t-edge-fault-tolerant Hamiltonian (resp., t-edge-fault-free Hamilton-connected) if G-F contains a Hamilton cycle (resp., is Hamilton-connected) for any F⊂E(G) with F⩽t. G is called t-fault-tolerant Hamiltonian (resp., t-fault-free Hamilton-connected) if G-F contains a Hamilton cycle (resp., is Hamilton-connected) for any F⊂E(G)∪V(G) with |F|⩽t.Lemma 4 (Huang and Xu [14]).
V
Q
n is (n-2)-edge-fault-tolerant Hamiltonian for n⩾2 and (n-3)-edge-fault-tolerant Hamilton-connected for n⩾3.In this paper, we will generalize this result by proving thatVQn is (n-2)-fault-tolerant Hamiltonian for n⩾2 and (n-3)-fault-tolerant Hamilton-connected for n⩾3.To prove our main results, we first prove the following result on the graphGn.Theorem 5.
Forn⩾3, Gn=Gn-10⊕MGn-11 is (n-3)-fault-tolerant Hamilton-connected for any perfect matching M between Gn-10 and Gn-11 defined by the rule in Definition 2.Proof.
We proceed by induction onn⩾3.
SinceG3≅Q3 or VQ3, which is vertex-transitive, it is easy to check the conclusion is true for n=3. Suppose now that n⩾4 and the result holds for any integer less than n. Let F⊂E(Gn)∪V(Gn) with F⩽n-3, and let x and y be two distinct vertices in Gn-F. We need to prove that Gn-F contains an xy-Hamilton path. Without loss of generality, we can assume F⊂V(Gn). Let Gn=L⊕MR, where (1)L=Gn-200⊕M1Gn-201,R=Gn-210⊕M2Gn-211,and let(2)FL=F∩L,FR=F∩R.By symmetry of structure of Gn, we may assume FL⩾FR.
Case 1 (
|
F
L
|
⩽
n
-
4
). In this case, by the hypothesis, we have |FR|⩽|FL|⩽n-4.
Subcase 1.1 (
x
,
y
∈
L
or
x
,
y
∈
R
). Without loss of generality, assume x,y∈R.
SinceR=Gn-1 and FR⩽n-4=(n-1)-3, by the induction hypothesis R-FR contains an xy-Hamilton path, say PR. Since VPR=2n-1-FR⩾2n-1-(n-4)>2(n-3)⩾2F, there is an edge uRvR in PR such that the neighbors uL and vL of uR and vR in L are not in F. Since L=Gn-1 and FL⩽n-4=(n-1)-3, by the induction hypothesis L-FL contains a uLvL-Hamilton path, say PL. Thus, PR-uRvR+uRuL+vRvL+PL is an xy-Hamilton path in Gn-F (see Figure 3(a)).
Subcase 1.2 (
x
∈
L
and
y
∈
R
).Since M=2n-1 and 2n-1-2>2(n-3)⩾2F, there is an edge uLuR∈M such that uL and uR are not in F∪{x,y}. By the induction hypothesis, let PL be an xuL-Hamilton path in L-FL, and let PR be a yuR-Hamilton path in R-FR. Then PL+uLuR+PR is an xy-Hamilton path in Gn-F (see Figure 3(b)).
Case 2 (
F
L
=
n
-
3
). In this case, |FR|=0.
Subcase 2.1 (
x
,
y
∈
L
). Arbitrarily take a vertex u∈FL. Since FL-u=n-4=(n-1)-3, by the induction hypothesis L-(FL-u) contains an xy-Hamilton path, say PL. Without loss of generality, assume u∈V(PL). Let uL and vL be two neighbors of u in PL, and let uLuR,vLvR∈M. By the induction hypothesis, R contains a uRvR-Hamilton path, say PR. Then PL-u+uLuR+vLvR+PR is an xy-Hamilton path in Gn-F.
Subcase 2.2 (
x
∈
L
and
y
∈
R
). If n=4, then L≅R≅Q3 or VQ3. Since |FL|=1 and L is vertex-transitive, we can assume FL={u}={000} unless x=000. It is easy to check that L-u contains a Hamilton cycle, say CL. Choose a neighbor uL of x in CL such that its neighbor uR in R is not y. By the induction basis, R contains a yuR-Hamilton path, say PR. Then, CL-xuL+uLuR+PR is an xy-Hamilton path in G4-F.
Assume nown⩾5; that is, n-2⩾3. Let F00=FL∩V(Gn-200),F01=FL∩V(Gn-201). Without loss of generality, we can assume F00≠∅.
(a)
y
∈
G
n
-
2
11
(See Figure4(a)). Arbitrarily take z11∈Gn-211 with z11≠y, and let z01z11∈M. Since n-2⩾3, by the induction hypothesis Gn-211 contains a z11y-Hamilton path, say P11. Arbitrarily take a vertex u∈F00. Since n⩾5, by the induction hypothesis L-(FL-u) contains an xz01-Hamilton path, say PL. If u is in PL, then let u00 and w00 be two neighbors of u in PL; if u is not in PL, then let u00v00 be an edge in PL. Let u00u10,v00v10∈M. By the induction hypothesis, Gn-210 contains a u10v10-Hamilton path, say P10. Let PL′=PL-u if u is in PL and PL′=PL-u00v00 if u is not in PL. Then P10+u00u10+v00v10+PL′+z01z11+P11 is an xy-Hamilton path in Gn-F (see Figure 4(a)).
(b)
y
∈
G
n
-
2
10
(See Figure4(b)). Arbitrarily take a vertex z01 in Gn-201-FL with z01≠x. Let z11 be the neighbor of z01 in Gn-211. Arbitrarily take a vertex u∈F00. Since n⩾5, by the induction hypothesis L-(FL-u) contains an xz01-Hamilton path, say PL. If u is in PL, then let u00 and w00 be two neighbors of u in PL; if u is not in PL, then let u00v00 be an edge in PL. Let u00u10,v00v10∈M. By the induction hypothesis, Gn-210 contains a u10v10-Hamilton path, say P10. Since y∈P10, we can write P10=P10(v10,y)+yw10+P10(w10,u10). Let w11 be the neighbor of w10 in Gn-211. By the induction hypothesis, Gn-211 contains a z11w11-Hamilton path, say P11. Let PL′=PL-u if u is in PL and PL′=PL-u00v00 if u is not in PL. Then PL′+u00u10+v00v10+P10-yw10+w10w11+P11+z01z11 is an xy-Hamilton path in Gn-F (see Figure 4(b)).
Subcase 2.3 (
x
,
y
∈
R
). If n=4, then L≅R≅G3. By the induction basis, R contains an xy-Hamilton path, say PR. Since G3 is vertex-transitive and |FL|=1, it is easy to check that L-FL contains a Hamilton cycle, say CL. Since L and R are 3-regular and isomorphic, there is an edge uRvR in PR which is not incident with x and y such that the corresponding edge eL in L is contained in CL. By Definition 2eL=uLvL, where uL and vL are neighbors of uR and vR in L, respectively. Thus, PR-uRvR+uLuR+vLvR+CL-eL is an xy-Hamilton path in G4-F (as a reference, see Figure 3(a)).
Assumen⩾5 below; that is, n-2⩾3.
(a)
x
,
y
∈
G
n
-
1
11
(See Figure5(a)). By the induction hypothesis, Gn-211 contains an xy-Hamilton path, say P11. Take u11v11∈E(P11), and let u01 and v01 be neighbors of u11 and v11 in Gn-201, respectively. Take a vertex u in F00. By the induction hypothesis, L-(FL-u) contains a u01v01-Hamilton path, say PL. If u is in PL, then let w00 and z00 be two neighbors of u in PL; if u is not in PL, then let w00z00 be an edge in PL. Let w10 and z10 be neighbors of w00 and z00 in Gn-210, respectively. By the induction hypothesis, Gn-210 contains a w10z10-Hamilton path, say P10. Let PL′=PL-u if u is in PL and PL′=PL-w00z00 if u is not in PL. Thus, P10+w00w10+z00z10+PL′+P11-u11v11+u01u11+v01v11 is an xy-Hamilton path in Gn-F (see Figure 5(a)).
(b)
x
∈
G
n
-
1
11
and
y
∈
G
n
-
2
10
(See Figure5(b)). Arbitrarily take a vertex u in F00 and an edge u00v00 in Gn-200. By the induction hypothesis, L-(FL-u) contains a u00v00-Hamilton path, say PL. If u is in PL, then let P′=PL-u+u00v00; if u is not in PL, then let P′=PL. Without loss of generality, assume that u is in PL and let u00 and v00 be two neighbors of u in PL.
Letu10 and v10 be neighbors of u00 and v00 in Gn-210, respectively. By the induction hypothesis, Gn-210 contains a u10v10-Hamilton path, say P10. Since y is in P10, we can write P10=P10(v10,y)+yw10+P10(w10,u10) (see Figure 5(b)). Let w11 be the neighbor of w10 in Gn-211. By the induction hypothesis, Gn-211 contains an xw11-Hamilton path, say P11. Then PL′+P10-yw10+w10w11+P11 is an xy-Hamilton path in Gn-F (see Figure 5(b)).
(c)
x
,
y
∈
G
n
-
2
10
(See Figure6)
(c1)
F
01
≠
0. By the induction hypothesis, Gn-210 contains an xy-Hamilton path, say P10. Take w10z10∈E(P10), and let w00 and z00 be neighbors of w10 and z10 in Gn-200, respectively. Take a vertex u in F01. By the induction hypothesis, L-(FL-u) contains a w00z00-Hamilton path, say PL. If u is in PL, let u00 and v00 be two neighbors of u in PL; if u is not in PL, let u00v00 be an edge in PL. Let PL′=PL-u if u is in PL and PL′=PL-u00v00 if u is not in PL.
Letu11 and v11 be neighbors of u01 and v01 in Gn-211, respectively. By the induction hypothesis, Gn-211 contains a u11v11-Hamilton path, say P11. Thus, P10-w10z10+w00w10+z00z10+PL′+u01u11+v01v11+P11 is an xy-Hamilton path in Gn-F (see Figure 6(a)).
(c2)
|
F
01
|
=
0. In this case, F00=F=n-3⩾2 since n⩾5. Consider the subgraph H of Gn induced by V(Gn-200)∪V(Gn-210). By Definition 2, it is easy to check that H=Gn-200⊕MGn-210. Let u∈F. By the induction hypothesis, H-(F-u) contains an xy-Hamilton path, say PH. Without loss of generality, assume that u is in PH. Let u00 and v00 be two neighbors of u in PH, and let u01 and v01 be two neighbors of u00 and v00 in Gn-201. Then there is a u01v01-Hamilton path in Gn-201, say P01. Take an edge w01z01 in P01, and let w11 and z11 be neighbors of w01 and z01 in Gn-211. Then there is a w11z11-Hamilton path in Gn-211, say P11. Thus, PH-u+P01-w01z01+P11 is an xy-Hamilton path in Gn-F (see Figure 6(b)).
The theorem follows.Figure 3
Illustrations of Case 1 in the proof of Theorem5.
(a)
x
,
y
∈
R
(b)
x
∈
L and y∈RFigure 4
Illustrations of Subcase 2.2 in the proof of Theorem5.
(a)
x
∈
L and y∈Gn-211
(b)
x
∈
L and y∈Gn-210Figure 5
Illustrations of Subcase 2.3 in the proof of Theorem5.
(a)
x
,
y
∈
G
n
-
2
11
(b)
x
∈
G
n
-
2
11 and y∈Gn-210Figure 6
Illustrations of Subcase 2.3(c) in the proof of Theorem5.
(a)
F
01
≠
0
(b)
F
01
=
0By Observation1 and Theorem 5, we have the following results immediately.Corollary 6.
V
Q
n is (n-3)-fault-tolerant Hamilton-connected for n⩾3.Corollary 7.
Every fault-free edge ofVQn is contained in a fault-free Hamilton cycle if the number of faults does not exceed n-2 and n⩾2.Proof.
Ifn=2, then the conclusion holds clearly. Assume now n⩾3. Let xy be a fault-free edge in VQn. Let F be a set of faults in VQn with F⩽n-2 and containing the edge xy. By Corollary 6, there is an xy-Hamilton path P in VQn-(F-xy). Then P+xy is a required cycle.



---

*Source: 513073-2015-01-22.xml*