Fault-tolerant Hamiltonian Laceability Of Cayley Graphs Generated By Transposition Cycles

An interconnection network is an signifcant partite of a computer and determinesthe property of computer. Since vertex or edge failures may happen in a network, it issignifcantly meaningful to consider fault tolerance of the network. In designing or select-ing a topological structure of an interconnection network, one fundamental considerationis the fault tolerance.Let Γ be a group and S be a subset of Γ such that1Γ∈/S and S1=S. The Cayleygraph Cay(Γ, S) is the graph with vertex set Γ and edge set {(a, ab)|a∈G, b∈S}.If a graph G has a path (a cycle) that contains all vertices of the graph G, then thepath (the cycle) is called a Hamiltonian path (a Hamiltonian cycle). If a graph G containsa Hamiltonian cycle, so G is Hamiltonian graph. A graph G is Hamiltonian connected ifthere exists a Hamiltonian path between any two vertices of G. For a bipartite graph, wesay it is Hamiltonian laceable if there is a Hamiltonian path between every pair of verticeswhich are in diferent partite sets.So far, the researchs on Cayley graphs mainly focus on the special group and diferentgenerating sets, such as the alternating group, the symmetric group, etc. For Cayley graphCay(Sn, S), Let Snbe the symmetric group on {1,2,···, n}, B be a minimal generatingset consisting of transpositions of Sn. Discussing the Hamilton of the kind of Cay(Sn, S),many scholars have put forward the concept of some application background and researchmethods. For example, M.Tchuente has proved that Cayley graph is Hamiltonian laceable,for n≥4. In [21], Li el al. have showed that Cayley graphs generated by transpositiontrees of are (n3)-edge fault-tolerant hamiltonian laceable for n≥4.In this paper, we also discuss Fault-tolerant Hamiltonian laceability of Cayley graphs.we will prove the Cayley graphs generated by transposition cycles are (n2)-edge fault-tolerant hamiltonian laceable for n≥6.