Small cycles, generalized prisms and Hamiltonian cycles in the Bubble-sort graph

Abstract

The Bubble-sort graph $B{S}_n,n⩾2$, is a Cayley graph over the symmetric group $Sy{m}_n$ generated by transpositions from the set $\{(12),(23),\dots ,(n-1n)\}$. It is a bipartite graph containing all even cycles of length $\ell$, where $4⩽\ell ⩽n!$. We give an explicit combinatorial characterization of all its $4$- and $6$-cycles. Based on this characterization, we define generalized prisms in $B{S}_n,n⩾5$, and present a new approach to construct a Hamiltonian cycle based on these generalized prisms.

13 pages, 7 figures