One conjecture of bubble-sort graphs |
| |
Authors: | Hai-zhong Shi Pan-feng Niu Jian-bo Lu |
| |
Affiliation: | College of Mathematics and Information Science, Northwest Normal University, Lanzhou 730030, Gansu, People?s Republic of China |
| |
Abstract: | 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?2, if n is odd then bubble-sort graph Bn is a union of edge-disjoint hamiltonian cycles; if n is even then bubble-sort graph Bn is a union of 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,6. |
| |
Keywords: | Interconnection networks Cayley graph Bubble-sort graph Decomposition of bubble-sort graphs Hamiltonian cycle |
本文献已被 ScienceDirect 等数据库收录! |