In mathematics, an edge cycle cover (sometimes called simply cycle cover[1]) 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.
YouTube Encyclopedic
-
1/3Views:29 44910 6195 666
-
[Discrete Math 2] Introduction to Graph Theory
-
Finding the Maximum Independent Set and Minimum Edge Cover
-
Graph Theory: 48. Complement of a Graph
Transcription
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. [2]
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.[3]
See also
References
- ^ Cun-Quan Zhang, Integer flows and cycle covers of graphs, Marcel Dekker,1997.
- ^ "Handbook in Graph Theory" (2004) ISBN 1-58488-090-2, p. 225
- ^ ""The Cycle Double Cover Conjecture"". Archived from the original on 2011-07-20. Retrieved 2008-12-21.
 | This graph theory-related article is a stub. You can help Wikipedia by expanding it. |
This page was last edited on 19 May 2024, at 11:46