Premium
Symmetric Hamilton cycle decompositions of complete graphs minus a 1‐factor
Author(s) -
Brualdi Richard A.,
Schroeder Michael W.
Publication year - 2011
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.20257
Subject(s) - combinatorics , mathematics , hamiltonian path , decomposition , bipartite graph , integer (computer science) , graph , complete graph , pancyclic graph , discrete mathematics , 1 planar graph , chordal graph , chemistry , computer science , programming language , organic chemistry
Let n ≥2 be an integer. The complete graph K n with a 1‐factor F removed has a decomposition into Hamilton cycles if and only if n is even. We show that K n − F has a decomposition into Hamilton cycles which are symmetric with respect to the 1‐factor F if and only if n ≡2, 4 mod 8. We also show that the complete bipartite graph K n, n has a symmetric Hamilton cycle decomposition if and only if n is even, and that if F is a 1‐factor of K n, n , then K n, n − F has a symmetric Hamilton cycle decomposition if and only if n is odd. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:1‐15, 2010