Paths And Cycles In Hypercubes And Folded Hypercubes

The hypercube and the folded hypercube are two kinds of classical internet model.Path system and cycle system is one of the focus of the structure and connectivity of internet.In this paper,we firstly study the edge disjoint paths in hypercubes and folded hypercubes with conditional fault.We introduce the F-strongly Menger edge connectivity of a graph,and show that in all n-dimensional hypercubes(folded hyper-cubes,respectively)with at most 2n-4(2n-2,respectively)edges removed,if each vertex has at least two fault-free adjacent vertices,then every pair of vertices u and v are connected by min{deg(u)} deg(v)} edge disjoint paths,where deg(u)and deg(v)are the remaining degree of vertices u and v,respectively.We call an edge-coloring of a graph G a rainbow coloring if the edges of G are colored with distinct colors.For every even positive integer k≥4,let f(n,k)denote the minimum number of colors required to color the edges of the n-dimensional cube Qn,so that every copy of k-cycle Ck is rainbow.Faudree et al.proved that f(n,4)= n for n = 4 or n>5.We consider f(n,6),give the number of 6-cycle in n-dimension hypercube and a lower bound of f(n,6).