# Bipancyclic Properties of Faulty Hypercubes

Authors: Chun-Nan Hung; Min-Kun Hsiao
Journal: ISRN Discrete Mathematics
 (2012)

---

## Abstract

A bipartite graphG=(V,E) is bipancyclic if it contains cycles of every even length from 4 to |V| and edge bipancyclic if every edge lies on a cycle of every even length from 4 to |V|. Let Qn denote the n-dimensional hypercube. Let F be a subset of V(Qn)∪E(Qn) such that F can be decomposed into two parts Fav and Fe, where Fav is a union of fav disjoint adjacent pairs of V(Qn), and Fe consists of fe edges. We prove that Qn-F is bipancyclic if fav+fe≤n-2. Moreover, Qn-F is edge bipancyclic if fav+fe≤n-2 with fav<n-2.


---

## Body

## 1. Introduction

Interconnection networks play an important role in parallel computing/communication systems. The graph embedding problem, which is a central issue in evaluating a network, asks if the guest graph is a subgraph of a host graph. A benefit of graph embedding is that we can apply an existing algorithm for guest graphs to host graphs. This problem has attracted a burst of studies in recent years. Note that cycle networks are useful for designing simple algorithms with low communication costs. Thus, there are many studies on the cycle embedding problem. The cycle embedding problem deals with identifying all possible lengths of the cycles in a given graph. For the graph definition and notation, we follow [1].Letu=unun-1⋯u2u1 be n-bit binary strings. The Hamming weight of u, denoted by w(u), is the number of i such that ui=1. Let u=unun-1⋯u2u1 and v=vnvn-1⋯v2v1 be two n-bit binary strings. The Hamming distanceh(u,v) between two vertices u and v is the number of different bits in the corresponding strings of both vertices. The n-dimensional hypercube, denoted by Qn, has all n-bit binary strings as its vertices; two vertices u and v are adjacent if and only if h(u,v)=1. Obviously, Qn is a bipartite graph with bipartition A={u∣w(u)iseven} and B={u∣w(u)isodd}. A vertex u of Qn is white if w(u) is odd, otherwise u is black. It is known that the distance between u and v is dQn(u,v)=h(u,v). For i=0, 1, let Qni denote the subgraph of Qn induced by {u=unun-1⋯u2u1∣uj=iforsome1≤j≤n}. Obviously, Qni is isomorphic to Qn-1. For any vertex u=unun-1…u2u1, we use (u)j to denote the bit uj. Moreover, we use (u)k to denote the vertex v=vnvn-1⋯v2v1 with vi=ui for 1≤i≠k≤n and vk=1-uk. An edge (u,v)∈E(Qn) is of dimensionk if v=(u)k.The hypercubeQn is one of the most popular interconnection networks for parallel computers/communication systems [2]. This is partly due to its attractive properties, such as regularity, recursive structure, vertex and edge symmetry, maximum connectivity as well as effective routing and broadcasting algorithms.Note that the hypercubeQn is a bipartite graph for every integer n. The corresponding cycle embedding problem on bipartite graphs is called the bipancyclic property. A bipartite graph G is bipancyclic if it contains cycles of every even length from 4 to |V(G)|, inclusive.There are some variations of the bipancyclic property. A bipartite graphG is edge bipancyclic if every edge lies on a cycle of every even length from 4 to |V(G)|, inclusive. A bipartite graph is k-edge fault tolerant bipancyclic if G-F is bipancyclic for any F⊂E(G) with |F|≤k. Moreover, a bipartite graph is k-edge fault tolerant edge bipancyclic if G-F is edge bipancyclic for any F⊂E(G) with |F|≤k. The following theorem is proved.Theorem 1.1 (see [3]).
Q
n is (n-2)-edge fault tolerant edge bipancyclic if n≥2.In this paper, we improve Theorem1.1 by considering both edge faults and vertex faults. However, we restrict the faults on the vertex set to those occurring only on disjoint adjacent pairs. Let F be a subset of V(Qn)∪E(Qn) such that F can be decomposed into two parts Fav and Fe where Fav is a union of fav disjoint adjacent pairs of Qn, and Fe consists of fe edges. More precisely, Fav=∪i=1fav{bi,wi}, where (bi,wi)∈E(Qn) and {bi,wi}∩{bj,wj}=∅ for i≠j. Without loss of generality, we assume that {bi∣1≤i≤fav} is a set of fav black vertices, and {wi∣1≤i≤fav} is a set of fav white vertices. We will prove that Qn-F is bipancyclic if fav+fe≤n-2. Moreover, Qn-F is edge bipancyclic if fav+fe≤n-2 with fav<n-2.


## 2. Preliminary

We need the following lemmas.Lemma 2.1 (see [4]).
Lete be any edge of Qn for n≥2. There are n-1 cycles of length four that contain e in common.Lemma 2.2 (see [5]).
Assume thatn is any positive integer with n≥2, and F is a subset of E(Qn) with |F|≤n-2. Then there exists a Hamiltonian path of Qn-F joining any two vertices from different bipartite sets. Moreover, there exists a Hamiltonian path joining y to z of Qn-F-{x} for x in some partite set and y,z in the other partite set for |F|≤n-3.Lemma 2.3 (see [6]).
Assume thatn is any positive integer with n≥2. Let u and x be two distinct white vertices of Qn and v and y be two distinct black vertices of Qn. There are two disjoint paths P1 and P2 such that (1) P1 joins u to v, (2) P2 joins x to y, and (3) P1∪P2 spans Qn.We extend the above lemma by considering the occurrence of edge faults.Lemma 2.4.
Assume thatn is any positive integer with n≥3, and F is a subset of E(Qn) with |F|≤n-3. Let u and x be two distinct white vertices of Qn and v and y be two distinct black vertices of Qn. There are two disjoint paths P1 and P2 of Qn-F such that (1) P1 joins u to v, (2) P2 joins x to y, and (3) P1∪P2 spans Qn-F.Proof.
We prove this lemma by induction onn. By Lemma 2.3, this lemma is true for n=3. Thus, we assume n≥4 and |F|≥1. For 1≤i≤n, let Fi denote the set of i-dimensional edges in F. Thus, ∑i=1n‍|Fi|=|F|. Without loss of generality, we assume that |Fn|≥1. For i=0, 1, we use Fi to denote the set E(Qni)∩F. Obviously, |Fi|≤n-4. Let Si={u,v,x,y}∩V(Qni) for i=0, 1. Without loss of generality, we can assume that |S0|≥|S1|. We have the following cases.
Case  1 (|S0|=4). By induction, there exist two spanning disjoint paths R1 and R2 of Qn0-F0 such that R1 joins u to v, and R2 joins x to y. Since 2n-1-2>2(n-3), there exists an edge (s,t) of R1 or R2 such that {(s,(s)n),(t,(t)n)}∩F=∅. Without loss of generality, we can assume that (s,t) is in R1. Thus, R1 can be written as 〈u,H1,s,t,H2,v〉. By Lemma 2.2, there exists a Hamiltonian path Q joining (s)n to (t)n of Qn1-F1. We set P1 as 〈u,H1,s,(s)n,Q,(t)n,t,H2,v〉 and set P2 as R2.
Case  2  (|S0|=3). Without loss of generality, we can assume that y∈Qn1. Since there are 2n-2 black vertices in Qn0 and 2n-2-1>n-3 for n≥4, there exists a black vertex z of Qn0 such that z≠v and (z,(z)n)∉F. By induction, there exist two spanning disjoint paths P1 and R1 of Qn0-F0 such that P1 joins u to v, and R1 joins x to z. By Lemma 2.2, there exists a Hamiltonian path R2 joining (z)n to y of Qn1-F1. We set P2 as 〈x,R1,z,(z)n,R2,y〉. Thus, P1 and P2 form the required paths.
Case  3  (|S0|=2andSi={u,v}forsomei=0,1). Without loss of generality, we can assume that S0={u,v}. By Lemma 2.2, there exists a Hamiltonian path P1 of Qn0-F0 joining u to v, and there exists a Hamiltonian path P2 of Qn1-F1 joining x to y. Obviously, P1 and P2 form the required paths.
Case  4  (|S0|=2andSi≠{u,v}foreachi=0,1). Without loss of generality, we can assume that S0={u,x}. Since there are 2n-2 black vertices in Qn0 and 2n-2>n-2 for n≥4, there exist two black vertices s and t of Qn0 such that {(s,(s)n),(t,(t)n)}∩F=∅. By induction, there exist two spanning disjoint paths Q1 and Q2 of Qn0-F0 such that Q1 joins u to s and Q2 joins x to t. Similarly, there exist two spanning disjoint paths R1 and R2 of Qn1-F1 such that R1 joins (s)n to v, and R2 joins (t)n to y. We set P1 as 〈u,Q1,s,(s)n,R1,v〉 and set P2 as 〈x,Q2,t,(t)n,R2,y〉.Lemma 2.5 (see [7]).
Assume thatn≥3. Let F be a subset of V(Qn)∪E(Qn) such that F can be decomposed into two parts Fav and Fe where Fav is a union of fav disjoint adjacent pairs of V(Qn) and Fe consists of fe edges. Then there exists a Hamiltonian cycle of Qn-F if fav+fe≤n-2.Lemma 2.6 (see [7]).
Assume thatn≥3. Let F be a subset of V(Qn)∪E(Qn) such that F can be decomposed into two parts Fav and Fe, where Fav is a union of fav disjoint adjacent pairs of V(Qn), and Fe consists of fe edges. Then there exists a Hamiltonian path of Qn-F between any two vertices from different partite sets of Qn if fav+fe≤n-3.We improve Lemma2.6 into the following lemma.Lemma 2.7.
Assume thatn≥3. Let F be a subset of V(Qn)∪E(Qn) such that F can be decomposed into two parts Fav and Fe, where Fav is a union of fav disjoint adjacent pairs of V(Qn), and Fe consists of fe edges. Then there exists a Hamiltonian path of Qn-F between any two vertices from different partite sets of Qn if fav+fe≤n-2 with fav≤n-3.Proof.
Letw be any fault-free white vertex and b be any fault-free black vertex. We need to construct a Hamiltonian path of Qn-F joining w to b by induction on n. Let H=Fe∪{(bi,wi)∣{bi,wi}⊂Fav}. For 1≤i≤n, let Hi denote the set of i-dimensional edges in H. Thus, ∑i=1n‍|Hi|=fe+fav. Without loss of generality, we assume that |Hn|=0.
By brute force, we can check that the required paths exist forn=3,4. By Lemmas 2.2 and 2.6, the required paths exist when fav=0 or fe+fav≤n-3. Therefore, we only need to consider the case fav≥1 and fav+fe=n-2 for n≥5. Thus, Fe≠∅. Let Fei=Fe∩E(Qni), Favi=Fav∩V(Qni), and Fi=Favi∪Fei for i=0, 1. Let b1 and w1 be a pair of Fav0 where b1 is a black vertex.
Case  1
(
F
⊄
Q
n
i
and
|
F
a
v
i
|
≤
n
-
4
,
for
i
=
0,1
)
.We first consider the case that w and b are in the same subcube. Without loss of generality, we can assume that both w and b are in Qn0. By induction, there exists a Hamiltonian path P1 of Qn0-F0 joining w to b. Note that l(P1)-4fav1=2n-1-2fav0-1-4fav1≥2n-1-4n+15>0. We can write P1 as 〈w,R1,u,v,R2,b〉 for some u and v such that {(u)n,(v)n}∩Fav1=∅. By induction, there exists a Hamiltonian path R3 of Qn1-F1 joining (u)n to (v)n. Thus, 〈w,R1,u,(u)n,R3,(v)n,v,R2,b〉 is a desired path.
Thus we consider the case thatw and b are in different subcubes. Without loss of generality, we can assume that w∈Qn0 and b∈Qn1. Since there are 2n-2 black vertices in Qn0 and 2n-2≥n-3 for n≥5, there exists a black vertex x in Qn0 such that {x,(x)n}∩Fav=∅. By induction, there exists a Hamiltonian path P1 of Qn0-F0 joining w to x and there exists a Hamiltonian path P2 of Qn1-F1 joining (x)n to b. Thus, 〈w,P1,x,(x)n,P2,b〉 is a desired path.
Case  2
(
F
⊂
Q
n
i or |Favi|=n-3 for some i=0,1). Without loss of generality, we can assume that F⊂Qn0 or |Fav0|=n-3. Thus, |Fav1|=0.
Assume that bothw and b are in Qn0. By induction, there exists a Hamiltonian path P1 of Qn0-(F-{b1,w1}) joining w to b. Suppose that the edge (b1,w1) is in P1. Without loss of generality, we can write P1 as 〈w,Z1,x,b1,w1,y,Z2,b〉. By Lemma 2.2, there exists a Hamiltonian path Z3 of Qn1-Fe1 joining (x)n to (y)n. Obviously, 〈w,Z1,x,(x)n,Z3,(y)n,y,Z2,b〉 is a desired Hamiltonian path. Thus, we consider the case that (b1,w1) is not in P1. Without loss of generality, P1 can be written as 〈w,R1,u,b1,v,R2,x,w1,y,R3,b〉. By Lemma 2.4, there are two disjoint spanning paths R4 and R5 of Qn1-Fe1 such that R4 joins (u)n to (x)n and R5 joins (v)n to (y)n of Qn1-Fe1. Obviously, 〈w,R1,u,(u)n,R4,(x)n,x,R2-1,v,(v)n,R5,(y)n,y,R3,b〉 is a desired path.
Now, we consider the case thatw and b are in different subcubes. Without loss of generality, we can assume that w∈Qn0 and b∈Qn1. By induction, there exists a Hamiltonian path P1 of Qn0-(F-{b1,w1}) joining w and b1. Suppose that the edge (b1,w1) is in P1. We can write P1 as 〈w,Z1,y,w1,b1〉. By Lemma 2.2, there exists a Hamiltonian path Z2 of Qn1-Fe1 joining (y)n to b. Obviously, 〈w,Z1,y,(y)n,Z2,b〉 is a desired path. Thus, we consider the case that (b1,w1) is not in P1. We can write P1 as 〈w,R1,u,w1,v,R2,x,b1〉. Assume that (x)n≠b. By Lemma 2.4, there are two disjoint spanning paths R3 and R4 of Qn1-Fe1 such that R3 joins (u)n to (x)n and R4 joins (v)n to b. Obviously, 〈w,R1,u,(u)n,R3,(x)n,x,R2-1,v,(v)n,R4,b〉 is a desired path. Assume that (x)n=b. By Lemma 2.2, there exists a Hamiltonian path R5 of Qn1-Fe1-{b} joining (u)n to (v)n. Obviously, 〈w,R1,u,(u)n,R5,(v)n,v,R2,x,(x)n=b〉 is a desired path.
Finally, we consider the case thatw and b are in Qn1. Let e=(x,y) be any faulty edge of F, where x is a white vertex. By Lemma 2.5, there exists a Hamiltonian cycle C1 of Qn0-(F-{e}).
Suppose thate is not an edge of C1. Since the length of C is at least 2n-1-2(n-3), we can write C1 as 〈u,Z1,v,u〉 such that {(u)n,(v)n}∩{w,b}=∅ and u is a white vertex. By Lemma 2.4, there exist two disjoint spanning paths Z2 and Z3 of Qn1-Fe1 such that Z2 joins w to (u)n and Z3 joins (v)n to b. Obviously, 〈w,Z2,(u)n,u,Z1,v,(v)n,Z3,b〉 is a desired path.
Thus, we consider the case thate is in C1. We can write C1 as 〈x,P1,y,x〉. Suppose that {(x)n,(y)n}∩{w,b}=∅. By Lemma 2.4, there exist two disjoint spanning paths P2 and P3 of Qn1-Fe1 such that P2 joins w to (x)n and P3 joins (y)n to b. Obviously, 〈w,P2,(x)n,x,P1,y,(y)n,P3,b〉 is a desired path. Suppose that |{(x)n,(y)n}∩{w,b}|=1. Without loss of generality, we assume that (x)n=b. By Lemma 2.2, there exists a Hamiltonian path P4 of Qn1-Fe1-{b} joining w to (y)n. Thus, 〈w,P4,(y)n,y,P1-1,x,(x)n=b〉 is a Hamiltonian path of Qn-F. Suppose that {(x)n,(y)n}={w,b}. Obviously, C1 can be written as 〈y,P5,u,v,P6,x,y〉 for some black vertex u. By induction, there exists a Hamiltonian path P7 of Qn1-Fe1-{w,b} joining (u)n to (v)n. Obviously, 〈w=(y)n,y,P5,u,(u)n,P7,(v)n,v,P6,x,(x)n=b〉 is a desired path.


## 3. Bipancyclic Properties

Theorem 3.1.
Assume thatn≥3. Let F be a subset of V(Qn)∪E(Qn) such that F can be decomposed into two parts Fav and Fe, where Fav is a union of fav disjoint adjacent pairs of V(Qn), and Fe consists of fe edges. Then Qn-F is bipancyclic if fav+fe≤n-2.Proof.
To prove this theorem, we will construct a cycle inQn-F of length t for every even integer with 4≤t≤2n-2fav by induction. Let H=Fe∪{(bi,wi)|{bi,wi}⊂Fav}. For 1≤i≤n, let Hi denote the set of i-dimensional edges in H. Thus, ∑i=1n|Hi|=fe+fav. Without loss of generality, we assume that |Hn|=0. Let Favi=Fav∩V(Qni),  Fei=Fe∩E(Qni), Fi=Favi∪Fei and favi=|Favi| for i=0, 1.
By brute force, we can check that the required cycles exist forn=3, 4. By Theorem 1.1, the required cycles exist if fav=0. Therefore, we consider the case fav≥1 and n≥5. Assume t is an even integer from 4 to 2n-2fav. Let Hi=H∩E(Qni) for i=0, 1. Without loss of generality, we can assume |H0|≥|H1|.
Suppose that|H0|≤n-3. We first consider the case that t≤2n-1-2fav1. By induction, the desired cycle exists in Qn1-F1. Suppose that t>2n-1-2fav1. Let C be a cycle of length 2n-1-2fav0 in Qn0-F0. Let t′=t-2n-1+2fav0-1. Note that there are 2n-1-2fav0+1 sections in C of length t′ depending on choice of the beginning and terminating vertices. Since 2n-1>4(n-2)≥2fav0+4fav1, one such section, say P, joins vertex p to vertex q such that {(p)n,(q)n}∩Fav1=∅. By Lemma 2.6, there exists a Hamiltonian path R of Qn1-F1 joining (q)n to (p)n. Obviously, 〈p,P,q,(q)n,R,(p)n,p〉 is a desired cycle.
Thus, we consider|H0|=n-2. Therefore, |H1|=0. Assume that 4≤t≤2n-1. By Theorem 1.1, the desired cycle exists in Qn1. Thus, we consider t>2n-1. Let {b1,w1} be a pair of adjacent vertices of Fav with b1 being a black vertex. By Lemma 2.5, there exists a Hamiltonian cycle C in Qn0-(H-{b1,w1}). Obviously, C can be written as 〈b1,P1,w1,P2,b1〉. Without loss of generality, we assume that l(P1)≤l(P2). Thus, 2n-2-fav0≤l(P2)≤2n-1-2fav0-1. We can write P2 as 〈w1,x,P2′,y,b1〉.
Suppose that2n-1<t≤2n-1+l(P2)-1. Let t′=t-2n-1-1. Let R be the section of P2′ joining vertex x to z of length t′. By Lemma 2.2, there exists a Hamiltonian path S of Qn1 joining (z)n to (x)n. Obviously, 〈x,R,z,(z)n,S,(x)n,x〉 is a desired cycle.
Suppose that2n-1+l(P2)<t≤2n-2fav. Since l(P1)+l(P2)=2n-1-2fav, l(P1)≥3. We can write P1 as 〈w1,u,P1′,v,b1〉. Let t′=t-2n-1-l(P2). Let T be the section of P1′ joining vertex u to c of length t′. By Lemma 2.4, there exist two spanning disjoint paths R1 and R2 of Qn1 such that R1 joins (y)n to (u)n and R2 joins (c)n to (x)n. Thus, 〈x,P2′,y,(y)n,R1,(u)n,u,T,c,(c)n,R2,(x)n,x〉 forms a desired cycle.
The theorem is proved.Theorem 3.2.
Assume thatn≥3. Let F be a subset of V(Qn)∪E(Qn) such that F can be decomposed into two parts Fav and Fe where Fav is a union of fav disjoint adjacent pairs of V(Qn) and Fe consists of fe edges. Then Qn-F is edge bipancyclic if fav+fe≤n-2 and fav≤n-3.Proof.
Lete=(u,v) be any fault-free edge of Qn where u is a black vertex. For 4≤t≤2n-2fav, we will construct a cycle containing (u,v) of length t in Qn-F by induction to prove this theorem. Suppose t=4, the desired cycle exists by Lemma 2.1. Thus, we consider t≥6.
LetH=Fe∪{(bi,wi)∣{bi,wi}⊂Fav}∪{(u,v)}. For 1≤i≤n, let Hi denote the set of i-dimensional edges in H. Since fe+fav≤n-2, we can assume without loss of generality that |Hn|=0. Thus, u,v are vertices in Qni for some i∈{0,1}. Let Favi=V(Qni)∩Fav and favi=|Favi| for i=0,1.
By Theorem1.1, the desired cycles exist if fav=0. Thus, the desired cycles exist for n=3. By brute force, we can check that the desired cycles exist for n=4. Thus, we only consider the case fav≥1 with n≥5. Without loss of generality, we can assume that fav0+fe0≥fav1+fe1.
Suppose thatfav0+fe0≤n-3 and fav0≤n-4. Without loss of generality, we can assume that both u and v are in Qn0. Suppose that 6≤t≤2n-1-2fav0. By induction, the desired cycle exists in Qn0-F0. Thus, we consider that 2n-1-2fav0+2≤t≤2n-2fav. Let t′=t-2n-1-2fav0-1. By induction, there exists a Hamiltonian cycle C of Qn0-F0 containing the edge (u,v). Since 2n-1>4(n-3)+1≥2fav0+4fav1+1, there exists an edge (x,y) in C such that {(x)n,(y)n}}∩Fav1=∅. Thus, C can be written as 〈u,v,P1,x,y,P2,u〉. By induction, there exist cycles 〈(x)n,Q,(y)n,(x)n〉 of length t′ of Qn1-F1. Obviously, 〈u,v,P1,x,(x)n,Q,(y)n,y,P2,u〉 forms the desired cycle.
Thus, we considerfav0+fe0=n-2 or fav0=n-3. We have the following two cases.
Case  1
(
(
u
,
v
)
∈
Q
n
1
). Suppose that 6≤t≤2n-1. By Theorem 1.1, the desired cycle exists. Thus, we consider t≥2n-1+2. Let b1 and w1 be a pair of adjacent vertices in Fav0. By induction, there exists a Hamiltonian cycle C in Qn0-Fe0-(Fav0-{b1,w1}) containing the edge (b1,w1). Thus, we can write C as 〈b1,w1,x,P,y,b1〉.
Suppose that2n-1+2≤t≤2n-2fav. Let t′=t-2n-1-1. Obviously, there exists a section P′ of P joining s and t of length t′ such that s is a black vertex. Suppose that {(s)n,(t)n}∩{u,v}=∅. By Lemma 2.4, there exist two spanning disjoint paths Q1 and Q2 of Qn1-Fe1 such that Q1 joins u to (s)n and Q2 joins (t)n to v. Obviously, 〈u,Q1,(s)n,s,P′,t,(t)n,Q2,v,u〉 forms the desired cycle. Suppose that |{(s)n,(t)n}∩{u,v}|=1. Without loss of generality, we assume that u=(t)n. By Lemma 2.2, there exists a Hamiltonian path Q of Qn1-Fe1-{u} joining (s)n to v. Obviously, 〈u=(t)n,t,P′-1,s,(s)n,Q,v,u〉 forms the desired cycle. Suppose that {(s)n,(t)n}={u,v}. Thus, u=(t)n and v=(s)n. We can write P′-1 as 〈t,R1,c,d,R2,s〉 for some c and d. By induction, there exists a Hamiltonian cycle C′ of Qn1-Fe1-{u,v} containing the edge ((c)n,(d)n). Thus, C′ can be written as 〈(c)n,Q′,(d)n,(c)n〉. Obviously, 〈u=(t)n,t,R1,c,(c)n,Q′,(d)n,d,R2,s,(s)n=v,u〉 forms the desired cycle.
Case  2
(
(
u
,
v
)
in
Q
n
0
). Suppose that 6≤t≤2n-1+2. Let t′=t-2. By Theorem 1.1, there exists a cycle C of length t′ in Qn1-Fe1 containing the edge ((u)n,(v)n). We can write C as 〈(u)n,(v)n,R,(u)n〉. Obviously, 〈u,v,(v)n,R,(u)n,u〉 forms the desired cycle.
Now, we consider2n-1+4≤t≤2n-2fav. Let b1 and w1 be a pair of adjacent vertices in Fav0. By induction, there exists a Hamiltonian cycle C in Qn0-Fe-(Fav-{b1,w1}) containing (u,v).
Suppose that(b1,w1)∈C. Obviously, C can be written as 〈w1,b1,y,P,x〉. Let t′=t-2n-1-1. Obviously, there exists a section Q of P joining s to t of length t′ containing (u,v). By Lemma 2.2, there exists a Hamiltonian path R joining (t)n to (s)n of Qn1-Fe1. Obviously, 〈s,Q,t,(t)n,R,(s)n,s〉 forms the desired cycle.
Suppose that(b1,w1)∉C. The cycle C can be written as 〈w1,x,P1,y,b1,s,P2,t,w1〉. Without loss of generality, we can assume that (u,v) is on the path P1. Suppose that 2n-1+4≤t≤2n-1+1+l(P1). Let t′=t-2n-1-1. There exists a section P1′ of P1 such that (1) P1′ joins c to d, (2) P1′ contains (u,v), and (3) P1′ is of length t′. By Lemma 2.2, there exists a Hamiltonian path R of Qn1-Fe1 joining (d)n to (c)n. Obviously, 〈c,P1′,d,(d)n,R,(c)n,c〉 forms the desired cycle. Suppose that 2n-1+3+l(P1)≤t≤2n-2fav. Let t′=t-2n-1-2-l(P1). There exists a section P2′ of P2 joining r to t of length t′. By Lemma 2.4, there exist two spanning disjoint paths  R1 and R2 of Qn1-Fe1 such that R1 joins (y)n to (r)n and R2 joins (t)n to (x)n. Obviously, 〈x,P1,y,(y)n,R1,(r)n,r,P2′,t,(t)n,R2,(x)n,x〉 forms the desired cycle.


## 4. Conclusion

In this paper, we study the bipancyclic property of faulty hypercubes. We improve previous results by considering both edge faults and vertex faults. LetF be a subset of V(Qn)∪E(Qn) such that F can be decomposed into two parts Fav and Fe where Fav is a union of fav disjoint adjacent pairs of V(Qn) and Fe consists of fe edges. We prove that Qn-F is bipancyclic if fav+fe≤n-2. This result is optimal. Let x be any vertex of Qn. Assume that F={(x,(x)i)∣1≤i≤n-1} forms a set of (n-1) faulty edges. Obviously, degQn-F(x)=1. Qn-F is not bipancyclic.We also prove thatQn-F is edge bipancyclic if fav+fe≤n-2 with fav<n-2. Again, this result is optimal. Assume that F=∪i=2n-1{(x)i,((x)1)i} forms a set of (n-2) adjacent faulty vertices. Obviously, degQn-F(x)=degQn-F((x)1)=2. Thus, any Hamiltonian cycle of Qn-F contains the path 〈(x)n,x,(x)1,((x)1)n〉. Therefore, there is no Hamiltonian cycle containing the edge ((x)n,((x)1)n) for n≥3. Thus, Qn-F is not edge bipancyclic.Two interesting observations, Lemmas2.4 and 2.7, are used in this paper. In the following, we claim that these two lemmas are also optimal.Letz, u, and x be three distinct white vertices of Qn. Assume that F={(z,(z)i)∣ for 2≤i≤n-1} forms a set of (n-2) faulty edges. It is observed that {(z)1,(z)n} are the neighbors of z in Qn-F. Moreover, (z)1 and (z)n are black vertices. Obviously, z cannot be any vertex in P1∪P2 for any two disjoint paths P1 and P2 of Qn-F such that P1 joins u to (z)1 and P2 joins x to (z)n. Therefore, there do not exist two disjoint paths P1 and P2 of Qn-F such that P1 joins u to (z)1 and P2 joins x to (z)n. Thus, the number of faulty edges of Lemma 2.4 is optimal.Assume thatn≥3. Let x be any vertex of Qn and F=∪i=2n-1{(x)i,((x)1)i} be a set of (n-2) adjacent faulty vertices. Obviously, (x)n and ((x)1)n are vertices in different partite sets. Assume that there is a Hamiltonian path P joining (x)n to ((x)1)n. Since degQn-F(x)=degQn-F((x)1)=2, P must include the section 〈(x)1,x,(x)n,((x)n)1〉. Obviously, P is not a Hamiltonian path and we get a contradiction. Thus, the number of adjacent faulty vertices of Lemma 2.7 is optimal.



---

*Source: 308595-2012-10-14.xml*