Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs

A bipartite graph G is bipancyclic if G has a cycle of length l for every even 4⩽l⩽|V(G)|. For a bipancyclic graph G and any edge e, G is edge-bipancyclic if e lies on a cycle of any even length l of G. In this paper, we show that the bubble-sort graph Bn is bipancyclic for n⩾4 and also show that it is edge-bipancyclic for n⩾5. Assume that F is a subset of E(Bn). We prove that Bn−F is bipancyclic, when n⩾4 and |F|⩽n−3. Since Bn is a (n−1)-regular graph, this result is optimal in the worst case.