Mutually Independent Hamiltonian Cycles in Some Graphs

Abstract

Let G = (V, E) be a hamiltonian graph. A hamiltonian cycle C of G is described as < v(1), v(2) ,..., v(n)(G), v(1)> to emphasize the order of vertices in C. Thus, v(1) is the beginning vertex and v(i) is the i-th vertex in C. Two hamiltonian cycles of G beginning at u, C-1 = < u(1), u(2),..., u(n(G)), u(1)> and C-2 = < v(1), v(2), ..., v(n(G),) v(1)) of G are independent if u(1) = v(1) = u, and u(i) not equal v(i) for every 2 <= i <= n(G). A set of hamiltonian cycles {C-1, C-2,..., C-k} of G are mutually independent if they are pairwise independent. The mutually independent hamiltonianicity of graph G, IHC(G), is the maximum integer k such that for any vertex u there are k-mutually independent hamiltonian cycles of G beginning at u. In this paper, we prove that IHC(C) <= delta(G) for any hamiltonian graph and IHC(G) >= 2 delta(G) - n(G) + 1 if delta(G) >= n(G)/2. Moreover, we present some graphs that meet the bound mentioned above.