CYCLES EMBEDDING ON FOLDED HYPERCUBES WITH FAULTY NODES??

Dan Yuan,Hongmei Liu,Maozheng Tang

(College of Science,Three Gorges University,Hubei 443002,PR China)

CYCLES EMBEDDING ON FOLDED HYPERCUBES WITH FAULTY NODES??

Dan Yuan?,Hongmei Liu,Maozheng Tang

(College of Science,Three Gorges University,Hubei 443002,PR China)

LetFFvbe the set of faulty nodes in ann-dimensional folded hypercubeFQnwith|FFv|≤n-1 and all faulty vertices are not adjacent to the same vertex.In this paper,we show that ifn≥4,then every edge ofFQn-FFvlies on a fault-free cycle of every even length from 6 to 2n-2|FFv|.

folded hypercube;interconnection network;fault-tolerant; path

2000 Mathematics Subject Classification

1 Introduction

Then-dimensional hypercubeQn(orn-cube)is one of the most important topology of networks due to its excellent properties such as regularity,recursive structure, small diameter,vertex and edge transitive and relatively short mean distance[1]. In order to improve the performance of hypercube,the folded hypercubeFQnhas been proposed[2].

Since a large-scale hypercube network,fails in any component,it’s desirable that the rest of the network continue to operate in spite of the failure.This leads to the graph-embedding problem with faulty edges and/or vertices.This problem has received much attention(see[3-10]).

The problem of embedding paths in ann-dimensional hypercube and folded hypercube has been well studied.Tsai[3]showed that for any subsetFvofV(Qn) with|Fv|≤n-2,every edge ofQn-Fvlies on a cycle of every even length from 4 to 2n-2|Fv|inclusive.Tsai[4]also showed that for any subsetFvofV(Qn)with|Fv|≤n-1 and all faulty vertices are not adjacent to the same vertex,every edge ofQn-Fvlies on a cycle of every even length from 6 to 2n-2|Fv|inclusive.Hsiehand Shen[5]proved that every edge ofQn-Fv-Felies on a cycle of every even length from 4 to 2n-2|Fv|even if|Fv|+|Fe|≤n-2,wheren≥3.

LetFFvandFFedenote the set of faulty nodes and faulty edges ofFQnrespectively.Hsieh,Kuo and Huang[6]proved that if the folded hypercubeFQnhas just only one fault node,thenFQncontains cycles of every even length from 4 to 2n-2 ifn≥3,and cycles of every odd length fromn+1 to 2n-1 whennis even,n≥2.Ma, Xu and Du[7]further demonstrated thatFQn-FFe(n≥3)with|FFe|≤2n-3 contains a fault-free cycle passing through all nodes if each vertex is incident with at least two fault-free edges.Kuo and Hsieh[8]improved the conclusion of[7]and proved thatFQn-FFewith|FFe|=2n-3 contains a fault-free cycle of every even length from 4 to 2n.Xu,Ma and Du[9]further showed that every fault-free edge ofFQn-FFelies on a fault-free cycle of every even length from 4 to 2nand every odd length fromn+1 to 2n-1 ifnis even,where|FFe|≤n-1.Then Cheng,Hao and Feng[10]proved that every fault-free edge ofFQn-FFvlies on a fault-free cycle of every even length from 4 to 2n-2|FFv|and every odd length fromn+1 to 2n-2|FFv|-1 ifnis even,where|FFv|≤n-2.

In this paper,under the conditional|FFv|≤n-1 and all faulty vertices are not adjacent to the same vertex,we show that ifn≥4,then every edge ofFQn-FFvlies on a fault-free cycle of every even length from 6 to 2n-2|FFv|.

2 Preliminaries

Please see[1]for graph-theoretical terminology and notation is not def i ned here. A network is usually modeled by a simple connected graphG=(V,E),whereV=V(G)(orE=E(G))is the set of vertices(or edges)ofG.We def i ne the vertexxto be a neighbor ofyifxy∈E(G).A graphGis bipartite ifX,Yare two disjoint subsets ofV(G)such thatE(G)={xy|x∈X,y∈Y}.A graphP=(u1,u2,···,uk) is called a path if the verticesu1,u2,···,ukare distinct and any two consecutive verticesuiandui+1are adjacent.u1andukare called the end-vertices ofP.Ifu1=uk,the pathP(u1,uk)is called a cycle(denoted byC).The length of a pathP(a cycleC),denoted byl(P)(orl(C)),is the number of edges inP(orC).In general,the distance of two verticesx,yis the length of the shortest(x,y)-path.

Then-dimensional hypercubeQn(or,n-cube)can be represented as an undirected graph with 2nvertices.Every vertexx∈Qnis labeled as a binary stringx1x2···xnof lengthnfrom 00···0 to 11···1.Two verticesuandvare adjacent if their binary strings dif f er in exactly one bit.For convenience,we calle∈Ean edge of dimensioniif its end-vertices strings dif f er inith-bit.In the rest of this paper,we denote,where=1-xi,xi=0,1.The Hammingdistance of two verticesx=x1x2···xnandy=y1y2···ynisH(x,y)the number of dif f erent bits between them.LetdH(x,y)be the shortest distance ofxandy.Note thatQnis a bipartite graph,and for any two distinct verticesx,yofQn,dH(x,y)=H(x,y).N(x)denotes a set of the nodes which are neighbors ofx.

As a variant of hypercube,then-dimensional folded hypercubeFQnis obtained by adding more edges between its vertices.

Def i nition 1 Then-dimensional folded hypercubeFQnis a graph withV(Qn)=V(FQn).Two verticesx=x1x2···xnandyare connected by an edge if and only if

Therefore,the hypercubeQnis a spanning subgraph of the folded hypercubeFQnobtained by removing the second type of edges(x∈V(FQn)),called complementary edges ofFQnand denoted by

In general,the f i rst type of edges are def i ned to be the hypercube edges,and denoted byEi={xxi},i=1,2,···,n.

Lemma 1An i-partition on FQn,where1≤i≤n,is a partition of FQnalong dimension i into two n-1-cubes,denoted byand.

()can also be denoted by0x(respectively,1x)for brevity,where satisfying0x=x1x2···xi···xn∈satisfying xi=0 (respectively,1x=x1x2···xi···xn∈satisfying xi=1).

Lemma 2[4]Let fe=0,fv=n-1,and every fault-free vertex is adjacent to at least two fault-free vertices in Qnfor n≥4.Then,every fault-free edge of Qnlies on a fault-free cycle of every even length from 6 to2n-2fvinclusive.

Lemma 3[3]Assume Fvis any subset of V(Qn).Every edge in Qn-Fvlies on a fault-free cycle of every even length from4to2n-2fvinclusive even if|Fv|≤n-2, where n≥3.

Lemma 4[12]Let n≥2be an integer.For any two dif f erent fault-free vertices u and v in Qnwith fe+fv≤n-2,there exists a fault-free uv-path of length l for each l satisfying dH(u,v)+2≤l≤2n-2fv-1and2|(l-dH(u,v)).Moreover, there must exist a fault-free uv-path of length dH(u,v)if dH(u,v)≥n-1.

Lemma 5[10]Assume that FQnis partitioned along dimension i(1≤i≤n)into two n-1-cubes,denoted byand,0u and0v(respectively,1u and1v)().If dH(0u,0v)=n-2(respectively,dH(1u,1v)=n-2),then dH(,1v)=1and dH(1u,)=1 (respectively,dH(,0v)=1and dH(0u,)=1);if dH(0u,0v)=1(respectively, dH(1u,1v)=1),then dH(,1v)=n-2and dH(1u,)=n-2(respectively,dH(,0v)=n-2and dH(0u,)=n-2).

Lemma 6[5]There exists a path of every odd length from 3 to2n-2|Fv|-1joining any two adjacent fault-free nodes in Qn-Fveven if|Fe|=0and|Fv|≤n-2, where n≥3.

Lemma 7[10]Assume n is even and FFvis any subset of V(FQn).Every edge of FQn-FFvlies on a fault-free cycle of every odd length from n+1to2n-2|FFv|-1inclusive even if|FFv|≤n-2,where n≥2.

Lemma 8Assume that FQnis partitioned along dimension i(1≤i≤n)into two n-1-cubes,denoted byand,0u and0v(respectively,1u and1v)().If dH(0u,0v)=n-3(respectively,dH(1u,1v)=n-3),then dH(,1v)=2and dH(1u,)=2(respectively,dH(,0v)= 2and dH(0u,)=2);if dH(0u,0v)=2(respectively,dH(1u,1v)=2),then dH(,1v)=n-3and dH(1u,)=n-3(respectively,dH(,0v)=n-3and dH(0u,)=n-3).

Proof IfdH(0u,0v)=n-3,thendH(u,v)=n-3,which impliesdH=2 anddH()=2,thusdH(,1v)=2 anddH(1u,)=2.By the similar discussion, ifdH(1u,1v)=n-3,thendH(,0v)=2 anddH(0u,)=2.

IfdH(0u,0v)=2,thendH(u,v)=2,which impliesdH()=n-3 anddH()=n-3,thusdH(,1v)=n-3 anddH(1u,)=n-3.By the similar discussion,ifdH(1u,1v)=2,thendH(,0v)=n-3 anddH(0u,)=n-3.The proof is completed.

Lemma 9[2]For any two vertices u,v∈Qn,if d(u,v)=k,then there are n internal disjoint paths from u and v such that there are k paths of length k and n-k paths of length k+2.

Lemma 10[10]Assume FFvis any subset of V(FQn).Every edge in FQn-FFvlies on a fault-free cycle of every even length from 4 to2n-2|FFv|inclusive even if |FFv|≤n-2,where n≥3.

Lemma 11[9]There is an automorphism σ of FQnsuch that σ(Ei)=Ejfor any i,j∈{1,2,···,n,c}.

3 Main Results

Before the proof,I give some symbols.FFvis the set of faulty vertices inFQnandis the set of faulty vertices in,i={0,1}.

Lemma 12Assume FFvis any subset of V(FQ4).Every edge in FQ4-FFvlies on a fault-free cycle of every even length from 6 to24-2|FFv|inclusive even if |FFv|≤3and all faulty vertices are not adjacent to the same vertex.

Proof If|FFv|=fv≤2,by Lemma 10,the lemma holds.Therefore,we only need to consider the situation offv=3,every edge inFQ4-FFvlies on a fault-free cycle of every even length from 6 to 10 inclusive.By Lemma 1,FQ4can be partitioned along dimensioniinto two 3-cubes,denoted byand.There must exist anisuch that(u),and(v),(We can simply divide one of the faulty vertex and the other faulty vertices into di ff erent partsor)along ani-dimension.The proof is the condition that all faulty vertices are not adjacent to the same vertex.We can consider extreme situation.Ifn-2 faulty vertices are adjacent to the same vertexx,we can choose one ofn-2 faulty vertices, denoted byy,thenxandyhave one bit dif f erently.So we can partition along this dimension.Thereforeyis in a part,other faulty vertices is in another part and all faulty vertices are not adjacent to the same vertex in this part).

Let=,i=0,1,.Without loss of generality, letFFv={w1,w2,w3},={w1,w2,={w3.=2,=1.eis a fault-free edge.=2,(u),,sodH(w1,w2)=1 ordH(w1,w2)=3.

(1).

Then,e∈C4,that is there exists a cycleC0of every even lengthl0containingein,wherel0=4.Let(x,y)/ebe a fault-free edge in cycleC0such that (xi,yi)(or)is fault-free in.LetC0=〈x,P0,y,x〉,then=l(P0)=3. Since=1,by Lemma 4,there exists a pathP1of every odd lengthl1joiningxiandyi(orand)in,where 3≤l1≤5.(xi,yi)(or)is fault-free,there exists a pathof every odd length joiningxiandyi(orand)in,where 15.LetC=〈x,P0,y,yi,xi,x〉orC=〈x,P0with even length.Since=3 and 15,6≤l≤10.

Through observation,e∈C6.Let(x,y)be a fault-free edge in cycleC0such that(xi,yi)(or)is fault-free in.LetC0=〈x,P0,y,x〉,then=l(P0),=5.Since=1,by Lemma 4,there exists a pathP1of every odd lengthl1joiningxiandyi(orand)in,where 3≤l1≤5.(xi,yi)(or)is fault-free,there exists a pathof every odd length joiningxiandyi(orand) in,where.LetC=〈x,P0,y,yi,xi,x〉orC=〈x,P0with even length.Sinceand,8≤l≤12.We can obtain the desired even cycle of length 6 inC0,wherel0=6.So 6≤l≤12.

(2)

Since=1,by Lemma 3,there exists a cycleC1of every even lengthl1containingein,where 4≤l1≤6.Let(x,y)be a fault-free edge in cycleC1such that(xi,yi)(or)is fault-free in.Hence,there exists a pathP1ofevery odd lengthjoiningxandyin,where.We can choose(xi,yi). SincedH(w1,w2)=1,(xi,yi)∈C4.(xi,yi)∈C4,(xi,yi)is fault-free,then there exists a pathP0of every odd lengthl0joiningxiandyi,where 1≤l0≤3.LetC=〈x,P1,y,yi,P0,xi,x〉with even length.Since 1≤l0≤3 and 35,6≤l≤10.

Since=1,by Lemma 3,there exists a cycleC1of every even lengthl1containingein,where 4≤l1≤6.Let(x,y)be a fault-free edge in cycleC1such that(xi,yi)(or)is fault-free in.Hence,there exists a pathP1of every odd lengthjoiningxandyin,where 35.dH(w1,w2)=3, through observation,(xi,yi)∈C6(or∈C6).We can choose(xi,yi),then, there exists a pathP0of every odd lengthl0joiningxiandyiin,wherel0=5. LetC=〈x,P1,y,yi,P0,xi,x〉with even length.Sincel0=5 and,10≤l≤12.LetC=〈x,P1,y,yi,xi,x〉with even length, where.Then 6≤l≤8.So 6≤l≤12.

(3)e∈Ei.

Let(x,y)be a fault-free edge in such that(xi,yi)is fault-free in

(x,y)∈C4,(x,y)is a fault-free edge,there exists a pathP0of every odd lengthl0joiningxandyin,where 1≤l0≤3.Since,by Lemma 4,there exists a pathP1of every odd lengthl1joiningxiandyiin,where 3≤l1≤5.LetC=〈x,P0,y,yi,P1,xi,x〉with even lengthl=l0+l1+2.Since 1≤l0≤3 and 3≤l1≤5,6≤l≤10.

Let(x,y)be a fault-free edge in such that(xi,yi)is fault-free in.Through observation,(x,y)∈C6,there exists a pathP0of every odd lengthl0joiningxandyin,wherel0=5.Since,by Lemma 4,there exists a pathP1of every odd lengthl1joiningxiandyiin,where 3≤l1≤5.LetC=〈x,P0,y,yi,P1,xi,x〉with even lengthl=l0+l1+2.Sincel0=5 and 3≤l1≤5,10≤l≤12.LetC=〈x,y,yi,P1,xi,x〉with even lengthl=1+l1+2.Since 3≤l1≤5,6≤l≤8. Therefore,6≤l≤12.

(4)e∈Ec.Lete=,

Letreplace{xi,yi},the following proof is similar to(3)e∈Ei.The proof is completed.

Theorem 1Assume FFvis any subset of V(FQn).Every edge in FQn-FFvlies on a fault-free cycle of every even length from 6 to2n-2|FFv|inclusive even if|FFv|≤n-1and all faulty vertices are not adjacent to the same vertex,where n≥4.

Proof If|FFv|=fv≤n-2,by Lemma 10,the theorem holds.Whenn=4, Lemma 12 holds.Therefore,we only need to consider the situation of|FFv|=fv=n-1,wheren≥5.By Lemma 1,FQncan be partitioned along dimensioniinto twon-1-cubes,denoted byand.There must exist anisuch that,and(v),(We can simply divide one of the faulty vertex and the other faulty vertices into dif f erent parts(or)along ani-dimension.The proof is the condition that all faulty vertices are not adjacent to the same vertex.We can consider extreme situation.Ifn-2 faulty vertices are adjacent to the same vertexx,we can choose one ofn-2 faulty vertices, denoted byy,thenxandyhave one bit dif f erently.So we can partition along this dimension.Thereforeyis in a part,other faulty vertices is in another part and all faulty vertices are not adjacent to the same vertex in this part).

Let,i=0,1,=n-1.eis a fault-free edge.

Case 1.1.

Since=n-2,by Lemma 2,there exists a cycleC0of every even lengthl0containingein,where.Let(x,y)be a fault-free edge in cycleC0such that(xi,yi)(or)is fault-free in(Since=1).LetC0=〈x,P0,y,x〉,then=l(P0),.Since,by Lemma 3,there exists a cycleC1of even lengthl1containing edge(xi,yi)(or)inwhere.Hence,there exists a pathP1of odd lengthjoiningxiandyi(orand),where.LetC=〈x,P0,y,yi,P1,xi,x〉orC=〈x,P01with even length.Sinceand,10≤l≤2n-2().We can obtain the desired even cycle of length from 6 to 8 inC0,where 6≤l0≤2n-1-.So 6≤l≤2n-2().

Case 1.2

Since,by Lemma 3,there exists a cycleC1of even lengthl1containing edgeein,where.LetCkbe a fault-freek-cycle covering the edgeein,where.Obviously,there aremutually disjoint edges excludingeinCk.2()is easy to be hold,where.Thus,there exists an(x,y)which is a fault-free edge in cycleC1such that(xi,yi)(or)is fault-free in.LetC1=〈x,P1,y,x〉, then=l(P1),32n-1--1.Since=n-2,and(xi,yi)(or)is fault-free edge,by Lemma 2,there exists a cycleC0of even lengthl0containing edge (xi,yi)(or)in,where 6≤l0≤2n-1-.Hence,there exists a pathP0of odd lengthjoiningxiandyi(orand),where 52n-1--1.LetC=〈x,P1,y,yi,P0,xi,x〉orC=〈x,P10with even lengthSinceand,10≤l≤2n-2(). We can obtain the desired even cycle of length from 6 to 8 inC1,where 4≤l1≤2n-1-.So 6≤l≤2n-2().

Case 1.3e∈Ei.

Lete=(x,xi).

Since=n-2=1,(u),,xhas at least 2 fault-free neighborsy1,y2in,one of themust be fault-free in. Therefore,there must exist an edge(x,y)insuch that(xi,yi)is fault-free in.Since=n-2,by Lemma 2,there exists a cycleC0of every even lengthl0containing(x,y)in,where 6≤l0≤2n-1-.LetC0=〈x,P0,y,x〉,then=l(P0),52n-1--1.Since=1,by Lemma 6,there exists a cycleP1of odd lengthl1joiningxiandyi,where 3≤l1≤2n-1--1.Since (xi,yi)is fault-free,there exists a cycleof odd lengthjoiningxiandyi,where.LetC=with even lengthSinceand,8≤l≤2n-2. LetC=〈x,y,yi,P1,xi,x〉withl=1+l(P1)+2,l(P1)=3,we can obtain the desired even cycle of length 6.So 6≤l≤2n-2().

Case 1.4e∈Ec.

The following proof is similar to Case 1.3.

Case 2.1.

Since3,by Lemma 3,there exists a cycleC0of every even lengthl0containing edgeein,where 4≤l0≤2n-1-.LetCkbe a fault-freek-cycle covering the edgeein,wherek=2n-1-.Obviously,there are 2n-2mutually disjoint edges excludingeinCk.2(2n-2)is easy to be hold, where3.Thus,there exists an(x,y)which is a fault-free edge in cycleCksuch that(xi,yi)(or)is fault-free in.Then,there exists a pathP0of every odd lengthjoiningxandyin,where. Since,by Lemma 3,there exists a cycleC1of every even lengthl1containing edge(xi,yi)(or)in,where 4≤l1≤2n-1-.(xi,yi)(oris fault-free edge,so there exists a pathP1of odd lengthjoiningxiandyi(orand),where.LetC=〈x,P0,y,yi,P1,xi,x〉orC=〈x,P01with even length.Since 3and,6≤l≤2n-.

Case 2.2.

The following proof is similar to Case 2.1.

Case 2.3e∈Ei.

By Lemma 11,the proof is completed.

Case 2.4e∈Ec.

By Lemma 11,the proof is completed.

The proof of Theorem 1 is f i nished.

4 Conclusion

The folded hypercubeFQnis an important network topology for parallel processing computer systems.According to[4],we can prove the same conclusion inFQn. Under the condition|FFv|≤n-1 and all faulty vertices are not adjacent to the same vertex,we show that ifn≥4,then every edge ofFQn-FFvlies on a fault-free cycle of every even length from 6 to 2n-2|FFv|.

[1]J.M.Xu,Graph and Application of Graphs,Dordrecht/Boston/London:Kluwer Academic publishers,2003.

[2]Y.Saad and M.H.Schultz,Topological properties of hypercubes,IEEE.Trans.on Comput.,37:7(1988),867-872.

[3]C.-H.Tsai,Cycles embedding in hypercubes with node failures,Information Processing Letters,102(2007),242-246.

[4]C.-H.Tsai,C.-R.Yu,Embedding various even cycles in a hypercube with node failures,The 24th Workshop on Combinatorial Mathematics and Computation Theory,2007, 237-243.

[5]S.-Y.Hsieh,T.-H.Shen,Edge-bipancyclicity of a hypercube with faulty vertices and edges,Discrete Applied Mathematics,156(2008),1802-1808.

[6]S.-Y.Hsieh,C.-N.Kuo,H.-L.Huang,1-vertex-fault-tolerant cycles embedding on folded hypercubes,Discrete Applied Mathematics,15(2009),3094-3098.

[7]M.J.Ma,J.M.Xu,Z.Z.Du,Edge-fault-tolerant hamiltonicity of folded hypercube,Journal of University of Science and Technology of China,36:3(2006),244-248.

[8]C.N.Kuo,S.Y.Hsieh,Pancyclicity and bipancyclicity of conditional faulty folded hypercubes,Information Sciences,180(2010),2904-2914.

[9]J.M.Xu,M.J.Ma,Z.Z.Du,Edge-fault-tolerant properties of hypercubes and folded hypercubes,Australasian Journal of Combinatorics,35(2006),7-16.

[10]D.Q.Cheng,R.X.Hao,Y.Q.Feng,Cycles embedding on folded hypercubes with faulty nodes,Discrete Applied Mathematics,161(2013),2894-2900.

[11]S.-Y.Hsieh,C.-N.Kuo,Hamiltonian-connectivity and strongly Hamiltonian-laceability of folded hypercubes,Computers and Mathematics with Applications,53(2007),1040-1044.

[12]M.Ma,G.Liu,X.Pan,Path embedding in faulty hypercubes,Applied Mathematics and Computation,192(2007),233-238.

[13]D.Q.Cheng,R.X.Hao,Y.Q.Feng,Embedding even cycles on folded hypercubes with conditional faulty edges,Information Processing Letters,115(2015),945-949.

[14]Weiping Han,S.Y.Wang,The g-Extra Conditional Diagnosability of Folded Hypercubes,Applied Mathematical Sciences,146:9(2015),7247-7254.

[15]D.Q.Cheng,R.X.Hao,Y.Q.Feng,Odd cycles embedding on folded hypercubes with conditional faulty edges,Information Sciences,282(2014),180-189.

(edited by Liangwei Huang)

?This project was supported by NSFC(11371162)and NSFC(11171129)and HuBei (T201103).

?Manuscript received

?Corresponding author.E-mail:1101358757@qq.com