The construction of mutually independent Hamiltonian cycles in bubble-sort graphs

Yuan-Kang Shih, Cheng-Kuan Lin, D. Frank Hsu, Jiann-Mean Tan, Lih-Hsing Hsu

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


A Hamiltonian cycle C=< u(1), u(2), ..., u(n(G)), u(1) > with n(G)=number of vertices of G, is a cycle C(u(1); G), where u(1) is the beginning and ending vertex and u(i) is the ith vertex in C and u(i)not equal u(j) for any i not equal j, 1 <= i, j <= n(G). A set of Hamiltonian cycles {C(1), C(2), ..., C(K)} of G is mutually independent if any two different Hamiltonian cycles are independent. For a hamiltonian graph G, the mutually independent Hamiltonianicity number of G, denoted by h(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. In this paper, we prove that h(B(n))=n-1 if n >= 4, where B(n) is the n-dimensional bubble-sort graph.
Original languageEnglish
Pages (from-to)2212-2225
Number of pages14
JournalInternational Journal of Computer Mathematics
Issue number10
StatePublished - 2010


  • Hamiltonian cycle; bubble-sort networks; interconnection networks; mutually independent Hamiltonian cycles; Cayley graph

Fingerprint Dive into the research topics of 'The construction of mutually independent Hamiltonian cycles in bubble-sort graphs'. Together they form a unique fingerprint.

Cite this