A bipartite graph G is bipancyclic if G has a cycle of length l for every even 4 \le \iota \le |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 \ge 4, and also show that it is edgebipancyclic for n \ge 5. To obtain this results, we also prove that we can construct a hamiltonian cycle of Bn that contains given two nonadjacent edges. Assume that F is the subset of E(Bn). We prove that Bn - F is bipancyclic whenever n \ge 4 and |F| \le n - 3. Since Bn is a (n - 1)-regular graph, this result is optimal in the worst case.
Citation:
Yosuke Kikuchi, Toru Araki, "Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs," ispan, pp.46-51, 8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05), 2005