### 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.

Original language | English |
---|---|

Pages (from-to) | 137-142 |

Number of pages | 6 |

Journal | Ars Combinatoria |

Volume | 106 |

State | Published - Jul 2012 |

### Keywords

- 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

Lin, C-K., Shih, Y-K., Tan, J-M., & Hsu, L. H. (2012). Mutually Independent Hamiltonian Cycles in Some Graphs.

*Ars Combinatoria*,*106*, 137-142.