Jump to content

Cycle decomposition (graph theory): Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
copyediting
No edit summary
Line 16: Line 16:
==Cycle decomposition of <math>K_n</math> and <math>K_n-I</math>==
==Cycle decomposition of <math>K_n</math> and <math>K_n-I</math>==


[[Brian Alspach]] and Heather Gavlas have 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.<ref>[http://www.sciencedirect.com/science/article/pii/S0095895600919968 Science Direct Article]</ref> Prior to this result the existence of cycle decompositions of a complete graph required the degree of the vertices to be even; therefore the complete graph must have an odd number of vertices. However, the authors were able to find a way to decompose a complete graph with an even number of vertices by removing a 1-factor. Their proof relies on Cayley graphs, in particular, circulant graphs. Also many of their decompositions come from the action of a [[permutation]] on a fixed subgraph.
[[Brian alspach]] and Heather Gavlas have 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.<ref>[http://www.sciencedirect.com/science/article/pii/S0095895600919968 Science Direct Article]</ref> Prior to this result the existence of cycle decompositions of a complete graph required the degree of the vertices to be even; therefore the complete graph must have an odd number of vertices. However, the authors were able to find a way to decompose a complete graph with an even number of vertices by removing a 1-factor. Their proof relies on Cayley graphs, in particular, circulant graphs. Also many of their decompositions come from the action of a [[permutation]] on a fixed subgraph.


They proved that for positive even integers <math>m</math> and <math>n</math> with <math>4\leq m\leq n </math>,the graph <math>K_n-I</math> (where <math>I</math> is a 1-factor) can be decomposed into cycles of length <math>m</math> if and only if the number of edges in <math>K_n-I</math> is a multiple of <math>m</math>. Also, for positive odd integers <math>m</math> and <math>n</math> with 3≤m≤n, the graph <math>K_n</math> can be decomposed into cycles of length m if and only if the number of edges in <math>K_n</math> is a multiple of <math>m</math>.
They proved that for positive even integers <math>m</math> and <math>n</math> with <math>4\leq m\leq n </math>,the graph <math>K_n-I</math> (where <math>I</math> is a 1-factor) can be decomposed into cycles of length <math>m</math> if and only if the number of edges in <math>K_n-I</math> is a multiple of <math>m</math>. Also, for positive odd integers <math>m</math> and <math>n</math> with 3≤m≤n, the graph <math>K_n</math> can be decomposed into cycles of length m if and only if the number of edges in <math>K_n</math> is a multiple of <math>m</math>.

Revision as of 01:44, 10 April 2014

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.

Preliminary definitions

Given a graph separate this graph into proper subgraphs in such a way that no two subgraphs have a common edge and the union of these subgraphs will give us the original graph. We call the set of these subgraphs the decomposition of .

A cycle decomposition is a decomposition such that each subgraph in the decomposition is a cycle. Every vertex in a graph that has a cycle decomposition must have even degree.

is a spanning subgraph of , if is obtained from graph only by the removal of edges. Therefore, graph has all the vertices of graph .

A spanning subgraph of a graph is called an r-factor of if is regular of degree . That is, all the vertices of have the same degree, namely r.

A spanning subgraph of graph is called a 1-factor of if is regular of degree 1. Thus, no two edges of a 1-factor share a vertex and there are no isolated vertices. To have a 1-factor, a graph must have an even number of vertices. 1-factors are also called matchings.

Cycle decomposition of and

Brian alspach and Heather Gavlas have 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] Prior to this result the existence of cycle decompositions of a complete graph required the degree of the vertices to be even; therefore the complete graph must have an odd number of vertices. However, the authors were able to find a way to decompose a complete graph with an even number of vertices by removing a 1-factor. Their proof relies on Cayley graphs, in particular, circulant graphs. Also many of their decompositions come from the action of a permutation on a fixed subgraph.

They proved that for positive even integers and with ,the graph (where is a 1-factor) can be decomposed into cycles of length if and only if the number of edges in is a multiple of . Also, for positive odd integers and with 3≤m≤n, the graph can be decomposed into cycles of length m if and only if the number of edges in is a multiple of .

References

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