Edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition-generating trees

Abstract

The Cayley graphs on the symmetric group plays an important role in the study of Cayley graphs as interconnection networks. Let Cay(S_n, B) be the Cayley graphs generated by transposition-generating trees. It is known that for any F⊂E(Cay(S_n, B)), if |F|≤n−3 and n≥4, then there exists a hamiltonian cycle in Cay(Sn, B)−F. In this paper, we show that Cay(S_n, B)−F is bipancyclic if Cay(S_n, B) is not a star graph, for n≥4 and |F|≤n−3.

Keywords:

• Cayley graphs
• symmetric group
• bipancyclicity
• edge-fault-tolerant bipancyclicity

2010 AMS Subject Classifications:

• 05A10
• 05C12
• 68M10

Acknowledgement

The research is supported by NSFC (No.11301371) and SXNSF.