Cycle decomposition (graph theory)

For the notation used to express permutations, see Cycle decomposition (group theory).

In graph theory, a cycle decomposition is a partitioning of the edges of a graph into subsets, such that the edges in each subset lie on a cycle.

References

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

Decomposition of a graph: In graph theory, Given a graph $G$ we can dissect this graph to proper subgraphs the way that no two subgraph would have the same edge and the union of these subgraph will give us the original graph. we can call these subgraphs the Decomposition of $G$.

cycle decomposition

In Graph Theory A cycle decomposition is a decomposition such that each subgraph $H_{i}$ in the decomposition is a cycle. Every vertex in a graph that has cycle decomposition must have even degree.

Spanning Subgraph: $H$ is a spanning subgraph of $G$, if $H$ is obtains by only edge dilation of graph$G$. Therefore Graph $H$ has all the vertices of graph $G$.

r-factor of a graph: A spanning subgraph $H$ of graph $G$ is called a r-factor of $G$ if $H$ is a regular if degree $r$. Therefore all vertices of $H$ shall have the same degree to be called r-factor.

1-factor of a graph: A spanning subgraph $H$ of graph $G$ is called a 1-factor of $G$ if $H$ is a regular if degree $r$. Therefore all vertices of $H$ shall have the same degree to be called 1-factor.

Cycle decomposition of $K_{n}$ & $K_{n}-I$ .

Brian Alspach and Heather Gavlas have established necessary and sufficient conditions for decomposition of the complete graph of even order minus a 1-factor into even cycles and the complete graph of odd order into odd cycles. Prior to this prove we know that the existence of cycle decomposition of a complete graph requires the degree of the vertices to be even; therefore the complete graph must have an odd degree of vertices. However Brian Alspach and Heather Gavlas were able to find a way to decompose a complete graph with an even number of vertices by removing a 1-factor. they used these following techniques to prove their theorems, Ceyley graphs, in particular, circulant graphs. Also many of their decompositions came from the action of a permutation on a fix subgraph.

They proved that for positive even integers $m$ and $n$ with $4\leq m\leq n$,the graph $K_{n}-I$ 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$.