Mutually Independent Hamiltonian Cycles in Some Graphs

Cheng-Kuan Lin, Yuan-Kang Shih, Jiann-Mean Tan, Lih Hsing Hsu

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.
Original languageEnglish
Pages (from-to)137-142
Number of pages6
JournalArs Combinatoria
StatePublished - Jul 2012


  • Hamiltonian cycle
  • Dirac theorem
  • mutually independent hamiltonian

Fingerprint Dive into the research topics of 'Mutually Independent Hamiltonian Cycles in Some Graphs'. Together they form a unique fingerprint.

Cite this