Cycle decomposition (graph theory)

For the notation used to express permutations, see Cycle decomposition (group 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 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≤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

This article is issued from Wikipedia - version of the Wednesday, September 02, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.