Search

The Bubble-Sort graph, denoted by(nis positive integer), is a special class of Cayley graph model. In 2009, Shi and Niu [Hamiltonian decomposition of some interconnection networks, inCombinatorial Optimization and Applications, D.-Z. Du, X. Hu, and P.M. Pardalos, eds., Springer, Huangshan, 2009, pp. 231–237.] proposed the following conjecture: (i) Ifnis odd thenis the union ofedge-disjoint Hamiltonian cycles. (ii) Ifnis even thenis the union ofedge-disjoint Hamiltonian cycles and a perfect matching. In this paper, we give a construction of the decomposition of Bubble-Sort graphwithnodd using the decomposition of. Moreover, if the decomposition ofis given using the decomposition ofthen the conjecture is proved. [ABSTRACT FROM AUTHOR]