Fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees

A bipartite graph is Hamiltonian laceable if there exists a Hamiltonian path joining every pair of vertices that are in different parts of the graph. It is well known that C a y ( S n , B ) is Hamiltonian laceable, where S n is the symmetric group on { 1 , 2 , … , n } and B is a generating set consisting of transpositions of S n . In this paper, we show that for any F ⊆ E ( C a y ( S n , B ) ) , if | F | ≤ n − 3 and n ≥ 4 , then there exists a Hamiltonian path in C a y ( S n , B ) − F joining every pair of vertices that are in different parts of the graph. The result is optimal with respect to the number of edge faults.