In mathematics, an edge cycle cover (sometimes called simply cycle cover) of a graph is a set of cycles which are subgraphs of G and contain all edges of G.
Contents
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 of G.
If the cycles of the cover have no edges in common, the cover is called edge-disjoint or simply disjoint cycle cover.
Minimum-Weight Cycle Cover
For a weighted graph, 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 bridgeless planar graphs the MWCCP can be solved in polynomial time.
Double cycle cover
The cycle double cover conjecture is an open problem in graph theory stating that in every bridgeless graph there exists a set of cycles that together cover every edge of the graph twice.