Cycle decomposition (graph theory)

Cycle decomposition of K n {displaystyle K_{n}} and K n − I {displaystyle K_{n}-I}

Brian Alspach and Heather Gavlas established necessary and sufficient conditions for the existence of a decomposition of a complete graph of even order minus a 1-factor into even cycles and a complete graph of odd order into odd cycles. Their proof relies on Cayley graphs, in particular, circulant graphs, and many of their decompositions come from the action of a permutation on a fixed subgraph.

They proved that for positive even integers m and n with 4 ≤ m ≤ n ,the graph K n − I (where I is a 1-factor) can be decomposed into cycles of length m if and only if the number of edges in K n − I is a multiple of m . Also, for positive odd integers m and n with 3≤m≤n, the graph K n can be decomposed into cycles of length m if and only if the number of edges in K n is a multiple of m .