One conjecture of bubble-sort graphs

The bubble-sort graph is an important interconnection network designed from Cayley graph model. One conjecture is proposed in Shi and Lu (2008) [10] as follows: for any integer n⩾2n⩾2, if n   is odd then bubble-sort graph BnBn is a union of n−12 edge-disjoint hamiltonian cycles; if n   is even then bubble-sort graph BnBn is a union of n−22 edge-disjoint hamiltonian cycles and its perfect matching that has no edges in common with the hamiltonian cycles. In this paper, we prove that conjecture is true for n=5,6n=5,6.

► We recall a conjecture on hamiltonian decomposition of bubble-sort graphs. ► We prove that conjecture is true for n=5,6n=5,6. ► The construction of the hamiltonian decomposition of B6B6 built using the hamiltonian decomposition of B5B5.