A note on Hamiltonian decomposition of Bubble-Sort graphs

Abstract

The Bubble-Sort graph, denoted by $B_n$ (n is positive integer), is a special class of Cayley graph model. In 2009, Shi and Niu [Hamiltonian decomposition of some interconnection networks, in Combinatorial Optimization and Applications, D.-Z. Du, X. Hu, and P.M. Pardalos, eds., Springer, Huangshan, 2009, pp. 231–237.] proposed the following conjecture: (i) If n is odd then $B_n$ is the union of $(n-1)/2$ edge-disjoint Hamiltonian cycles. (ii) If n is even then $B_n$ is the union of $(n-2)/2$ edge-disjoint Hamiltonian cycles and a perfect matching. In this paper, we give a construction of the decomposition of Bubble-Sort graph $B_{n+1}$ with n odd using the decomposition of $B_n$. Moreover, if the decomposition of $B_n$ is given using the decomposition of $B_{n-1}$ then the conjecture is proved.

Keywords:

• Bubble-Sort graph
• Hamiltonian decomposition
• Cayley graph

2010 AMS Subject Classifications:

• 05C45
• 05C38

Acknowledgments

The authors would like to greatly thank the referees for their valuable comments and suggestions that considerably improved the quality of the paper.

Disclosure statement

No potential conflict of interest was reported by the authors.