Hamilton cycle rich two‐factorizations of complete graphs

For all integers n  ≥ 5, it is shown that the graph obtained from the n ‐cycle by joining vertices at distance 2 has a 2‐factorization is which one 2‐factor is a Hamilton cycle, and the other is isomorphic to any given 2‐regular graph of order n . This result is used to prove several results on 2‐factorizations of the complete graph K n of order n . For example, it is shown that for all odd n  ≥ 11, K n has a 2‐factorization in which three of the 2‐factors are isomorphic to any three given 2‐regular graphs of order n , and the remaining 2‐factors are Hamilton cycles. For any two given 2‐regular graphs of even order n , the corresponding result is proved for the graph K n ‐ I obtained from the complete graph by removing the edges of a 1‐factor. © 2004 Wiley Periodicals, Inc.