ABSTRACT
In Section 9.5, we discussed the concept of mutually independent Hamiltonian paths. Obviously, we can extend this concept into mutually independent Hamiltonian cycles. A Hamiltonian cycle C of graph G is described as 〈u1, u2, . . . , un(G), u1〉 to emphasize the order of vertices in C. Thus, u1 is the beginning vertex and ui is the ith vertex in C. Two Hamiltonian cycles of G beginning at a vertex x, C1 =〈u1, u2, . . . , un(G), u1〉 and C2 =〈v1, v2, . . . , vn(G), v1〉, are independent if x= u1 = v1 and ui = vi for every i, 2≤ i≤ n(G). A set of Hamiltonian cycles {C1,C2, . . . ,Ck} of G are mutually independent if any two different Hamiltonian cycles are independent. The mutually independent Hamiltonianicity of graph G, IHC(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. Obviously, IHC(G)≤ δ(G) if G is a Hamiltonian graph.
