109
Views
0
CrossRef citations to date
0
Altmetric
Original Articles

A note on Hamiltonian decomposition of Bubble-Sort graphs

&
Pages 1074-1077 | Received 21 Sep 2014, Accepted 01 Apr 2015, Published online: 26 May 2015
 

Abstract

The Bubble-Sort graph, denoted by Bn (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 Bn is the union of (n1)/2 edge-disjoint Hamiltonian cycles. (ii) If n is even then Bn is the union of (n2)/2 edge-disjoint Hamiltonian cycles and a perfect matching. In this paper, we give a construction of the decomposition of Bubble-Sort graph Bn+1 with n odd using the decomposition of Bn. Moreover, if the decomposition of Bn is given using the decomposition of Bn1 then the conjecture is proved.

2010 AMS Subject Classifications:

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.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.