Symmetric hamilton cycle decompositions of complete graphs minus a 1-factor

摘要

Let nequiv;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 n2, 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.