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$

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .