Cycle decomposition (graph theory)

In graph theory, a cycle decomposition is a decomposition (a partitioning of a graph's edges) into cycles. Every vertex in a graph that has a cycle decomposition must have even degree.

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

References

• Bondy, J.A.; Murty, U.S.R. (2008), "2.4 Decompositions and coverings", Graph Theory, Springer, ISBN 978-1-84628-969-9 .