One conjecture of bubble-sort graphs
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 B(n) is a union of n-1/2 edge-disjoint hamiltonian cycles; if n is even then bubble-sort graph B(n) is a union of n-2/2 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. (C) 2011 Elsevier B.V. All rights reserved.
bubble-sort graph interconnection networks cayley graph hamiltonian cycle decomposition of bubble-sort graphs