In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, 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 and
Brian Alspach
Brian Roger Alspach is a mathematician whose main research interest is in graph theory. Alspach has also studied the mathematics behind poker, and writes for ''Poker Digest ''and ''Canadian Poker Player'' magazines.
Biography
Brian Alspach was bo ...
and Heather Gavlas established necessary and sufficient conditions for the existence of a decomposition of a
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...
of even order minus a
1-factor (a
perfect matching
In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
) into even cycles and a complete graph of odd order into odd cycles.
Their proof relies on
Cayley graphs, in particular,
circulant graphs, and many of their decompositions come from the action of a
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
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
, the graph
can be decomposed into cycles of length
if and only if the number of edges in
is a multiple of
.
References
*.
Graph theory
{{combin-stub