Cycles Embedding in d-Ary n-Dimensional Cube With Node Failures*

LI Zhaoxiang

(College of Science，Minzu University of China，Beijing，100081，China)

Abstract：The d-ary n-dimensional cube (the general form of hypercube) has been widely used as the interconnection network in parallel computers.The fault-tolerant capacity of an interconnection network is a critical issue in parallel computing.In this article,we consider the fault-tolerant capacity of the d-ary n-dimensional cube.Let F be a set of faulty vertices in Qn(d) (n≥3) with |F|≤n-2,we prove that every fault-free edge and fault-free vertex (node) of Qn(d) lies on a fault-free cycle of every even length from 4 to dn-2|F|.Moreover,if d is an odd number,every fault-free edge and fault-free vertex (node) of Qn(d) lies on a fault-free cycle of length dn-2|F|.

Key words：cycle embedding，hypercube，fault-tolerant，interconnection network,d-ary

0 Introduction

Network topology is usually represented by a graph where vertices represent processor and edges represent links between processors[1].The hypercube has been widely used as the interconnection network in parallel computers[2,3].Then-dimensional generalized hypercube,denoted byQ(d1,d2,…,dn),wheredi(≥2) is an integer for eachi=1,2,…,n.The vertex-set ofQ(d1,d2,…,dn) is the setV={x1x2…xn:xi∈{0,1,…,di-1},i=1,2,…,n} and two verticesx=x1x2…xnandy=y1y2…ynare linked by an edge if and only if they differ exactly in one coordinate.Ifd1=d2=…=dn=d≥2,thenQ(d,d,…,d) is called thed-aryn-dimensional cube,denoted byQn(d).It is clear thatQn(2) is hypercubeQn.For two verticesuandvinQn(d),the Hamming distanceh(u,v) between two verticesuandvis the number of different bits in the corresponding strings of both vertices; and the distance betweenuandv,denoted byD(Qn(d);u,v),is the length of the shortest path betweenuandv.Obviously,h(u,v)=D(Qn(d);u,v).Letu=u1u2…unbe a vertex ofQn(d),uj(a)=v=v1v2…vnis also a vertex ofQn(d),vi=ui(1≤i≤n,i≠j,j∈{1,2,…,n}),vj≠uj,vj=a∈{0,1,2,…,d-1}.A vertex is fault-free if it is not faulty.An edge is fault-free if the two end-vertices and the link between them are not faulty.A cycle of lengthkis calledk-cycle.A graphGis vertex-transitive if for any given pair (x,y) of vertices inGthere is someθ∈Aut(G)(Aut(G) is an automorphism group ofG) such thaty=θ(x).

The cycle embedding problem deals with all possible lengths of the cycles in a given graph，it is investigated in a lot of interconnection networks[4].The fault-tolerant capacity of an interconnection network is a critical issue in parallel computing[2].For hypercubeQn,Saad and Schultz[5]proved that an even cycle of lengthkexists for each even integer between 4 and 2n.Letfe(respectively,fv) be the number of faulty edges (respectively,vertices) inQn.Iffe≤n-2,Li et al.[1]proved that every fault-free edge ofQn(n≥3) lies on a fault-free cycle of every even length from 4 to 2n.Iffe≤n-1 and all faulty edges are not incident with the same vertex,Xu et al.[6]showed that every fault-free edge ofQn(n≥4) lies on a fault-free cycle of every even length from 6 to 2n.Fu[7]proved that a fault-free cycle of length with at least 2n-2fvcan be embedded inQnwithfv≤2n-4.Iffv≤2n-2,Tsai[2]proved that every fault-free edge and fault-free vertex ofQnlies on a fault-free cycle of every even length from 4 to 2n-2fv.Stewart and Xiang[8]studied the bipanconnectivity and bipancyclicity ink-aryn-cubes.Cheng et al.[9]studied the vertex-fault-tolerant cycles embedding in balanced hypercubes with faulty edges; Hao et al.[10]studied the hamiltonian cycle embedding for fault tolerance in balanced hypercubes.

In this article,we study the cycle embedding inQn(d).For any subsetFofV(Qn(d))(n≥3) with |F|≤n-2,we prove that every fault-free edge and fault-free vertex (node) ofQn(d) lies on a fault-free cycle of every even length from 4 todn-2|F|.Ifd=2,these results are the results of Tsai[2].

1 Preliminaries

LetVnbe the set of vertices ofQn(d).For a giveni(0≤i≤d-1),letiVn-1be the subset of vertices ofQn(d) whose fist coordinate isi.Thus the set of vertices ofQn(d) can be decomposed intoddisjoint subsets 0Vn-1,1Vn-1,…,(d-1)Vn-1.We useiQn-1(d) to denote the subgraph ofQn(d) induced byiVn-1.TheniQn-1(d) is isomorphic toQn-1(d).It is often convenient to writeQn(d)=0Qn-1(d)Θ1Qn-1(d)Θ…Θ(d-1)Qn-1(d).

ProofLetu=u1u2…unandv=v1v2…vn.Sinceuandvare distinct vertices,there is an indexj(j∈{1,2,…,n} such thatuj≠vj,uj∈{0,1,…,d-1},vj∈{0,1,…,d-1}.Therefore,Qn(d) can be partitioned along dimensionjintodcopiesQn-1(d) such that one containsuand the other containsv.

2 d is an even number

Theorem1Letxandybe any two vertices inQn(d)(n≥2) andlbe any integer withD(Qn(d);x,y)≤l≤dn-1.Ifdis an even number andl-D(Qn(d);x,y) is also an even number,then there is anxy-path of lengthlinQn(d).

ProofLetD(Qn(d);x,y)=m.The proof is based on the recursive structure ofQn(d) by induction onn≥2.Whenn=2,ifD(Q2(d);x,y)=1.By the vertex-transitivity ofQ2(d)[3],without loss of generality,we can assumex=00,y=01.

x=00→01=y,x=00→02→03→01=y,x=00→02→03→04→05→01=y,…,x=00→02→03→04→05→…→0(d-2)→0(d-1)→01=yare thexy-path of lengthl=1,3,5,…,d-1 inQ2(d).

x=00→10→12→02→03→04→05→…→0(d-2)→0(d-1)→01=y.x=00→10→20→22→12→02→03→04→05→…→0(d-2)→0(d-1)→01=y.….x=00→10→20→30→40→…→(d-2)0→(d-1)0→(d-1)2→(d-2)2→…→22→12→02→03→04→05→…→0(d-2)→0(d-1)→01=y.….x=00→10→20→30→40→…→(d-2)0→(d-1)0→(d-1)2→(d-2)2→…→22→12→02→03→13→23→…→(d-2)3→(d-1)3→(d-1)4→(d-2)4→…→24→14→04→05→…→0(d-1)→1(d-1)→2(d-1)→…→(d-2)(d-1)→(d-1)(d-1)→(d-1)1→(d-2)1→…→21→11→01=yare thexy-path of lengthl=d+1,d+3,…,3(d-1),…,d2-1 inQ2(d).

Whenn=2,ifD(Q2(d);x,y)=2.By the vertex-transitivity ofQ2(d)[3],without loss of generality,we can assumex=00,y=11.

x=00→10→11=y,x=00→20→30→10→11=y.x=00→20→30→40→50→10→11=y.….x=00→20→30→40→50→…→(d-2)0→(d-1)0→10→11=yare thexy-path of lengthl=2,4,6,…,dinQ2(d).

x=00→01→21→20→30→40→50→…→(d-2)0→(d-1)0→10→11=y.x=00→01→02→22→21→20→30→40→50→…→(d-2)0→(d-1)0→10→11=y.….x=00→01→02→…→0(d-2)→0(d-1)→2(d-1)→2(d-2)→…→22→21→20→30→40→…(d-3)0→(d-2)0→(d-1)0→10→11=y.….x=00→01→02→…→0(d-2)→0(d-1)→2(d-1)→2(d-2)→…→22→21→20→30→31→32→…→3(d-2)→3(d-1)→4(d-1)→4(d-2)→…→42→41→40→…→(d-3)0→(d-3)1→(d-3)2→…→(d-3)(d-2)→(d-3)(d-1)→(d-2)(d-1)→(d-2)(d-2)→…→(d-2)2→(d-2)1→(d-2)0→(d-1)0→(d-1)2→(d-1)3→…→(d-1)(d-2)→(d-1)(d-1)→1(d-1)→1(d-2)→…→13→12→10→11=yare thexy-path of lengthl=d+2,d+4,…,3d-2,…,d2-2 inQ2(d).

Assuming the theorem holds for anykwith 2≤k

Case1m

By the vertex-transitivity ofQn(d)[3],without loss of generality,we can assumex,y∈V(0Qn-1(d)).By the induction hypothesis,there is anxy-path of lengthlinQn(d),wherem≤l≤dn-1-1.

Assumingdn-1≤l≤2×dn-1-1.LetP0be the longestxy-path in 0Qn-1(d),the length ofP0islP0andlP0-mis an even number.We havelP0=dn-1-1 ifmis odd andlP0=dn-1-2 ifmis even.Letl1=l-lP0-1.Thenl1is odd and less thandn-1.Letuvbe any edge inP0,andu,v∈0Qn-1(d),u≠x,u≠y,v≠x,v≠y.ThenP0=P0xu+uv+P0vy.Letu′ andv′ be neighbors ofuandvin 1Qn-1(d).By the induction hypothesis,there is au′v′-pathP1of lengthl1in 1Qn-1(d).ThenP0xu+uu′+P1+v′v+P0vyis anxy-path of lengthlin 0Qn-1(d)Θ1Qn-1(d),this is also anxy-path of lengthlinQn(d).

…,…,…

Case2m=n

By the vertex-transitivity ofQn(d)[3],without loss of generality,we can assumex∈V(0Qn-1(d)),y∈V(1Qn-1(d)).Letvbe a neighbor ofyin 1Qn-1(d),ube the neighbor ofvin 0Qn-1(d).ThenD(Qn-1(d);x,u)=n-2.

Ifn≤l≤dn-1+1.By the induction hypothesis,there is anxu-pathPof lengthl-2 in 0Qn-1(d),ThenP+uv+vyis anxy-path of lengthlinQn(d).

Ifdn-1+2≤l≤2×dn-1-1.LetP0be the longestxu-path in 0Qn-1(d),the length ofP0islP0andlP0-mis an even number.We havelP0=dn-1-1 ifmis odd andlP0=dn-1-2 ifmis even.Letl1=l-lP0-1.Thenl1is odd and less thandn-1.By the induction hypothesis,there is avy-pathP1of lengthl1in 1Qn-1(d).ThenP0+uv+P1is anxy-path of lengthlin 0Qn-1(d)Θ1Qn-1(d),this is also anxy-path of lengthlinQn(d).

The rest of the proof is similar to Case 1.

By the induction principle,the theorem follows.

Applying Theorem 1,we have

Corollary1For anyn≥2,every edge ofQn(d)(d≥2,dis an even number) lies on a cycle of every even length from 4 todn.

Applying Theorem 1.Ifd=2,we have

Corollary2[1,3]Letxandybe any two vertices inQn(n≥2) andlbe any integer withD(Qn;x,y)≤l≤2n-1.Ifl-D(Qn;x,y) is an even number,then there is anxy-path of lengthlinQn.

LetFbe a set of faulty vertices inQn(d).

Lemma3For any subsetFofV(Q2(d))(d≥4,dis an even number) with |F|≤1,every edge ofQ2(d)-Flies on a fault-freek-cycle,k=4,6,…,d2-2|F|.

Lemma4For any subsetFofV(Q3(d))(d≥2,dis an even number) with |F|≤1,every edge ofQ3(d)-Flies on a fault-freek-cycle,k=4,6,…,d3-2|F|.

Similar to Lemma 4,we have

Theorem2Letn≥3 be an integer andQn(d)(d≥2,dis an even number) has exactly one faulty vertex.Then,every fault-free edge ofQn(d) lies on a fault-free cycle of every even length from 4 todn-2.

Theorem3Letn≥3 be an integer.For any subsetFofV(Qn(d))(d≥2,dis an even number) with |F|=fv≤n-2,every edge ofQn(d)-Flies on a cycle of every even length from 4 todn-2fv.

ProofWe prove this theorem by induction onn.By Lemma 4,Theorem 3 holds forn=3.Assuming that the theorem is true for every integerk(3≤k≤n).LetFbe a subset ofV(Qk+1(d)) and |F|=fv.By Corollary 1 and Theorem 2,Theorem 3 holds forfv≤1.Thus,we only consider the case of 2≤fv≤n-2.

Since |F|≤n-2 and the degree of any vertex ofQn(d) isn(d-1),any fault-free vertex ofQn(d) has at leastn(d-2)+2 fault-free neighbors.Thus,every fault-free vertex can be incident by a fault-free edge.Therefore,we have

Corollary3Letn≥3 be an integer.For any subsetFofV(Qn(d))(d≥2,dis an even number) with |F|≤n-2,every vertex ofQn(d)-Flies on a fault-free cycle of every even length from 4 todn-2|F|.

Applying Theorem 3.Ifd=2,we have

Corollary4[2]Assuming thatn≥3.For any subsetFofV(Qn(d)) with |F|=fv≤n-2,every edge ofQn(d)-Flies on a cycle of every even length from 4 to 2n-2fv.

Applying Corollary 4.We have

Corollary5[2]Letn≥3 be an integer.For any subsetFofV(Qn(d)) with |F|≤n-2,every vertex ofQn-Flies on a fault-free cycle of every even length from 4 to 2n-2|F|.

3 d is an odd number

Theorem4Letxandybe any two vertices inQn(d)(n≥2) andlbe any integer withD(Qn(d);x,y)≤l≤dn-1.Ifdis an odd number,l-D(Qn(d);x,y) is an even number,then there is anxy-path of lengthlinQn(d).Moreover,ifD(Qn(d);x,y)=1,there is anxy-path of lengthl=dn-1 inQn(d).

ProofLetD(Qn(d);x,y)=m.The proof is based on the recursive structure ofQn(d) by induction onn≥2.

Whenn=2,ifD(Qn(d);x,y)=1.By the vertex-transitivity ofQ2(d)[3],without loss of generality,we can assumex=00,y=01.

x=00→01=y,x=00→02→03→01=y,x=00→02→03→04→05→01=y,…,x=00→02→03→04→05→…→0(d-3)→0(d-2)→01=yare thexy-path of lengthl=1,3,5,…,d-2 inQ2(d).

x=00→10→12→02→03→04→05→…→0(d-3)→0(d-2)→01=y,x=00→10→20→22→12→02→03→04→05→…→0(d-3)→0(d-2)→01=y,….

x=00→10→20→30→40→…→(d-2)0→(d-1)0→(d-1)2→(d-2)2→…→22→12→02→03→13→23→…→(d-2)3→(d-1)3→(d-1)4→(d-2)4→…→24→14→04→…→0(d-4)→1(d-4)→2(d-4)→…→(d-2)(d-4)→(d-1)(d-4)→(d-1)(d-3)→(d-2)(d-3)→…→2(d-3)→1(d-3)→0(d-3)→0(d-2)→1(d-2)→2(d-2)→…→(d-2)(d-2)→(d-1)(d-2)→(d-1)1→(d-2)1→…→21→11→01=y,….

x=00→10→20→30→40→…→(d-2)0→(d-1)0→(d-1)2→(d-2)2→…→22→12→02→03→13→23→…→(d-2)3→(d-1)3→(d-1)4→(d-2)4→…→24→14→04→…→0(d-4)→1(d-4)→

2(d-4)→…→(d-2)(d-4)→(d-1)(d-4)→(d-1)(d-3)→(d-2)(d-3)→…→2(d-3)→

1(d-3)→0(d-3)→0(d-2)→1(d-2)→2(d-2)→…→(d-2)(d-2)→(d-1)(d-2)→(d-1)1→(d-1)(d-1)→(d-2)(d-1)→(d-2)1→(d-3)1→(d-3)(d-1)→(d-4)(d-1)→(d-4)1→…→21→2(d-1)→1(d-1)→11→01=yare thexy-path of lengthl=d,d+2,…,d2-d-1,…,d2-2 inQ2(d).

x=00→10→20→30→40→…→(d-2)0→(d-1)0→(d-1)2→(d-2)2→…→22→12→02→03→13→23→…→(d-2)3→(d-1)3→(d-1)4→(d-2)4→…→24→14→04→…→0(d-4)→1(d-4)→

2(d-4)→…→(d-2)(d-4)→(d-1)(d-4)→(d-1)(d-3)→(d-2)(d-3)→…→2(d-3)→1(d-3)→0(d-3)→0(d-2)→1(d-2)→2(d-2)→…→(d-2)(d-2)→(d-1)(d-2)→(d-1)1→(d-1)(d-1)→(d-2)(d-1)→(d-2)1→(d-3)1→(d-3)(d-1)→(d-4)(d-1)→(d-4)1→…→21→2(d-1)→0(d-1)→1(d-1)→11→01=yis thexy-path of lengthl=d2-1 inQ2(d).

The rest of the inductive proof are similar to Theorem 1.

Applying Theorem 4,we have

Corollary6For anyn≥2,every edge ofQn(d)(d≥3,dis an odd number) lies on a cycle of every even length from 4 todn-1.Moreover,every edge ofQn(d) lies on a cycle of lengthdn.

Similar to Lemma 3.We have

Lemma5For any subsetFofV(Q2(d))(d≥3,dis an odd number) with |F|≤1,every edge ofQ2(d)-Flies on a fault-freek-cycle,k=4,6,…,d2-2|F|-1.Moreover,every edge ofQ2(d)-Flies on a fault-free (d2-2|F|)-cycle.

Similar to Lemma 4,applying Theorem 4 and Lemma 5.We have

Lemma6For any subsetFofV(Q3(d))(d≥3,dis an odd number) with |F|≤1,every edge ofQ3(d)-Flies on a fault-freek-cycle,k=4,6,…,d3-2|F|-1.Moreover,every edge ofQ3(d)-Flies on a fault-free (d3-2|F|)-cycle.

Similar to Lemma 6,we have

Theorem5Letn≥3 be an integer andQn(d)(d≥3,dis an odd number) has exactly one faulty vertex.Then,every fault-free edge ofQn(d) lies on a fault-free cycle of every even length from 4 todn-3.Moreover,every fault-free edge ofQn(d) lies on a fault-free cycle of lengthdn-2.

Theorem6Letn≥3 be an integer.For any subsetFofV(Qn(d))(d≥3,dis an odd number) with |F|=fv≤n-2,every edge ofQn(d)-Flies on a cycle of every even length from 4 todn-2fv-1.Moreover,every edge ofQn(d)-Flies on a cycle of lengthdn-2fv.

ProofWe prove this theorem by induction onn.By Lemma 6,Theorem 6 holds forn=3.Assuming that the theorem is true for every integerk(3≤k≤n).LetFbe a subset ofV(Qk+1(d)) and |F|=fv.By Corollary 6 and Theorem 5,Theorem 6 holds forfv≤1.Thus,we only consider the case of 2≤fv≤n-2.

The proof of Case 2 is similar to the proof of Case 2 of Theorem 3.

Applying Theorem 6,we have

Corollary7Letn≥3 be an integer.For any subsetFofV(Qn(d))(d≥3,dis an odd number) with |F|≤n-2,every vertex ofQn(d)-Flies on a fault-free cycle of every even length from 4 todn-2|F|.Moreover,every vertex ofQn(d)-Flies on a fault-free cycle of lengthdn-2|F|.