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

Abstract

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.