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, \ldots, 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, \ldots, u_{n(G),u_1})\) and \(C_2 = (v_1, v_2, \ldots, v_{n(G)},v_1)\) of \(G\) are independent if \(u_1 = v_1 = u_1\) and \(u_i \neq v_i\) for every \(2 \leq i \leq n(G)\). A set of hamiltonian cycles \(\{C_1, C_2, \ldots, C_k\}\) of \(G\) are mutually independent if they are pairwise independent. The mutually independent hamiltonianicity of graph \(G\), \(\text{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 \(\text{IHC}(G) \geq \delta(G)\) for any hamiltonian graph and \(\text{IHC}(G) \geq 2\delta(G) – n(G) + 1\) if \(\delta(G) \geq \frac{n(G)}{2}\). Moreover, we present some graphs that meet the bound mentioned above.