2
$\begingroup$

http://mathworld.wolfram.com/HamiltonDecomposition.html

In the 1890s, Walecki showed that complete graphs K_n admit a Hamilton decomposition for odd n, and decompositions into Hamiltonian cycles plus a perfect matching for even n (Lucas 1892, Bryant 2007, Alspach 2008).

I was wondering if there is a simple method to decompose $K_{2n}$ into one matching (1-factor) and $n-1$ hamiltonian cycles (connected 2-factors)?

I tried to read some papers. The [Lucas 1892] paper was french! The [Alspach 2008] was printed in Bulletin of ICA, which does not have a digital version. And the [Bryant 2007] survey was too long and had a more general theorem about decomposition of $K_n$ or $K_n-I$ into m-cycles, depending on the relation of n and m.

As you may know, decomposition of $K_{2n}$ into matchings (1-factor decomposition) and decomposition of $K_{2n+1}$ into hamiltonian cycles have very simple geometric-ish methods (form a regular polygon with a vertex inside and each turn consider edges parallel or perpendicular to some line). Have you heard of any simple method to decompose $K_{2n}-I$ ($K_{2n}$ minus a matching) into hamiltonian cycles?

$\endgroup$
2
$\begingroup$

In a 1-factor decomposition of $K_{2n}$ which you describe (an edge from the center of a regular $(2n-1)$-gon to a vertex and all chords perpendicular to it), two matchings which correspond to `almost opposite' edges from the center form a Hamiltonian cycle. After you collect $n-1$ such pairs (by rotating one of them), one matchong remains.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.