In
mathematics, an edge cycle cover (sometimes called simply cycle cover) of a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
is a family of
cycle
Cycle, cycles, or cyclic may refer to:
Anthropology and social sciences
* Cyclic history, a theory of history
* Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr.
* Social cycle, various cycles in so ...
s which are
subgraphs of ''G'' and contain all edges of ''G''.
If the cycles of the cover have no vertices in common, the cover is called vertex-disjoint or sometimes simply disjoint cycle cover. In this case the set of the cycles constitutes a
spanning subgraph
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Symbols
A
B
...
of ''G''.
If the cycles of the cover have no edges in common, the cover is called edge-disjoint or simply disjoint cycle cover.
Properties and applications
Minimum-Weight Cycle Cover
For a
weighted graph
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* ...
, the Minimum-Weight Cycle Cover Problem (MWCCP) is the problem to find a cycle cover with minimal sum of weights of edges in all cycles of the cover.
For
bridge
A bridge is a structure built to span a physical obstacle (such as a body of water, valley, road, or rail) without blocking the way underneath. It is constructed for the purpose of providing passage over the obstacle, which is usually somethi ...
less
planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...
s the MWCCP can be solved in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
.
Cycle k-cover
A cycle ''k''-cover of a graph is a family of cycles which cover every edge of ''G'' exactly ''k'' times. It has been proven that every bridgeless graph has cycle ''k''-cover for any integer even integer ''k≥4''. For ''k=2'', it is the well-known
cycle double cover conjecture is an open problem in graph theory. The
cycle double cover conjecture states that in every
bridgeless graph there exists a set of cycles that together cover every edge of the graph twice.
"The Cycle Double Cover Conjecture"
/ref>
See also
*Alspach's conjecture Alspach's conjecture is a mathematical theorem that characterizes the disjoint cycle covers of complete graphs with prescribed cycle lengths. It is named after Brian Alspach, who posed it as a research problem in 1981. A proof was published by .
...
*Vertex cycle cover In mathematics, a vertex cycle cover (commonly called simply cycle cover) of a graph ''G'' is a set of cycles which are subgraphs of ''G'' and contain all vertices of ''G''.
If the cycles of the cover have no vertices in common, the cover is call ...
References
{{reflist
Graph theory objects
Combinatorial optimization