On mutually independent hamiltonian cycles

In a graph G, two cycles C-1 = < u(1), u(2), ... , u(m), u(1)> and C-2 = < v(1), v(2), ... ,v(m), v(1)> beginning at a vertex s are independent if u(1) = v(1) = s and u(i) not equal v(i) for 2 <= i <= m; k cycles beginning at s, where k >= 3, are mutually independent if every two distinct cycles are independent. A graph G is said to contain k mutually independent hamiltonian cycles if there exist k hamiltonian cycles in G beginning at any vertex s such that the k hamiltonian cycles are mutually independent. In this paper, we use n for the number of vertices and e for the number of edges in graph G. And we use (e) over bar for the number of edges in the complement of G. Let G be a graph with n >= 3 and (e) over bar <= n - 3. We show that G contains n - 3 mutually independent hamiltonian cycles if (e) over bar = 1, and contains n - 1 - (e) over bar mutually independent hamiltonian cycles, otherwise. Both bounds are shown to be sharp.