Edge cycle cover
In graph theory, a branch of mathematics, an edge cycle cover (sometimes called simply cycle coverCun-Quan Zhang, Integer flows and cycle covers of graphs, Marcel Dekker,1997.) of a graph is a family of cycles 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 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, 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."Handbook in Graph Theory" (2004) {{isbn|1-58488-090-2}}, [https://books.google.com/books?id=mKkIGIea_BkC&dq=%22minimum+weight+cycle+cover%22&pg=PA225 p. 225]
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 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.{{Cite web |url=http://www.cems.uvm.edu/%7Earchdeac/problems/cyclecov.htm |title="The Cycle Double Cover Conjecture" |access-date=2008-12-21 |archive-date=2011-07-20 |archive-url=https://web.archive.org/web/20110720105312/http://www.cems.uvm.edu/%7Earchdeac/problems/cyclecov.htm |url-status=dead }}