Cycle decomposition (graph theory) explained

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.^[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

m and n with 4 \leq m\leq 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 \leq m\leq 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 .

References

• .

Notes and References

1. 10.1006/jctb.2000.1996 . 81 . Cycle Decompositions of K _{n} and K _{n{-}I}   . 2001 . Journal of Combinatorial Theory, Series B . 77–99 . Alspach . Brian. free .