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 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 {\displaystyle m} 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.
References
Alspach, Brian (2001). "Cycle Decompositions of Kn and Kn−I". Journal of Combinatorial Theory, Series B. 81: 77–99. doi:10.1006/jctb.2000.1996.
Bondy, J.A.; Murty, U.S.R. (2008), "2.4 Decompositions and coverings", Graph Theory, Springer, ISBN 978-1-84628-969-9.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
