Cycle decomposition (graph theory)

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 (a perfect matching) into even cycles and a complete graph of odd order into odd cycles.^[1] 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 ${\displaystyle m}$ and ${\displaystyle n}$ with ${\displaystyle 4\leq m\leq n}$, the graph ${\displaystyle K_{n}-I}$ (where ${\displaystyle I}$ is a 1-factor) can be decomposed into cycles of length ${\displaystyle m}$ if and only if the number of edges in ${\displaystyle K_{n}-I}$ is a multiple of ${\displaystyle m}$. Also, for positive odd integers ${\displaystyle m}$ and ${\displaystyle n}$ with ${\displaystyle 3\leq m\leq n}$, the graph ${\displaystyle K_{n}}$ can be decomposed into cycles of length ${\displaystyle m}$ if and only if the number of edges in ${\displaystyle K_{n}}$ is a multiple of ${\displaystyle m}$.

The problem of decomposing an Eulerian graph into a minimum number of edge-disjoint cycles is NP-complete, as is the corresponding problem of decomposing into a maximum number of cycles.^[2]

An Eulerian graph has a unique number of cycles in all of its cycle decompositions if and only if no two edge-disjoint cycles in the graph share more than two vertices. This property can be decided in polynomial time: there exists an algorithm running in time ${\displaystyle {\mathcal {O}}(n(n+m))}$ that determines whether the cycle number of a given Eulerian graph is unique, where ${\displaystyle n}$ is the number of vertices and ${\displaystyle m}$ is the number of edges.^[2]