Fault-tolerance Hamiltonian Laceable Of A Kind Of Network

Using graph to study the topology of the network has been widely ac-cepted and applied by computer scientists. Hamiltonian path (resp.cycle) isan important concept in graph theory. Studied first by Kirkman[1856], Hamil-tonian cycles are named for Sir William Hamilton, who described a game onthe graph of the dodecahedron in which one player specifies a 5-vertex pathand the other must extend it to a spanning cycle.A Hamiltonian path (resp. cycle) of graph G is a path (resp. cycle)which meets every vertex of G. A graph with Hamiltonian cycle is called aHamiltonian graph, or Hamiltonian. A graph G is Hamiltonian connectedif there exists a Hamiltonian path between any two vertices of G. For abipartite graph, we say it is Hamiltonian laceable if there is a Hamiltonianpath between every pair of vertices which are in di?erent partite sets [19].Let G be a group and S be a subset of G such that 1G∈/ S and S^-1 = S.The Cayley graph Cay(S : G) is the graph with vertex set G and edge set{(g,gs)| g∈G,s∈S}. Let Sn be the symmetric group on {1,2,···,n}, Bbe a minimal generating set consisting of transpositions of Sn. It is shown byKompel makher and Liskovets [13] that Cay(B : S_n) is Hamiltonian.In this paper, we show that Cay(B : S_n) - F has a Hamiltonian path be-tween any two vertices of di?erent partite sets if F∈E(Cay(B : S_n)) and |F|≤n - 3. The result is optimal with respect to the number of edge faults.