Premium
Hamilton cycle rich two‐factorizations of complete graphs
Author(s) -
Bryant Darryn
Publication year - 2004
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.20005
Subject(s) - mathematics , combinatorics , graph , factorization , hamiltonian path , complete graph , pancyclic graph , discrete mathematics , chordal graph , 1 planar graph , algorithm
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.