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

Abstract

A Hamiltonian cycle C=⟨ u ₁, u ₂, …, u _n(G), u ₁ ⟩ with n(G)=number of vertices of G, is a cycle C(u ₁; G), where u ₁ is the beginning and ending vertex and u _i is the ith vertex in C and u _i ≠u _j for any i≠j, 1≤i, j≤n(G). A set of Hamiltonian cycles {C ₁, C ₂, …, 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.

Keywords:

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

2000 AMS Subject Classifications :

• 05C38
• 05C45
• 05C75
• 05C90
• 68M10

Acknowledgements

The authors are grateful to the referees for their thorough reviews of the paper and many helpful suggestions. Jimmy J. M. Tan was partially supported by the National Science Council of the Republic of China under contract NSC 96-2221-E-009-137-MY3 and also by the Aiming for the Top University and Elite Research Center Development Plan.