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 I of G. In this paper, we show that the bubble-sort graph B_n is bipancyclic for n≥ 4, and also show that it is edge-bipancyclic for n≥5. To obtain this results, we also prove that we can construct a hamiltonian cycle of B_n that contains given two nonadjacent edges. Assume that F is the subset of E(B_n). We prove that B_n -F is bipancyclic whenever n ≥4 and |F|≤ n-3. Since B_n is a (n-1)-regular graph, this result is optimal in the worst case.