1. A note on Hamiltonian decomposition of Bubble-Sort graphs.
- Author
-
Beggas, Fairouz and Neggazi, Brahim
- Subjects
- *
HAMILTONIAN systems , *MATHEMATICAL decomposition , *GRAPH theory , *CAYLEY graphs , *COMBINATORIAL optimization - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF