Edge cycle cover

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.

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]

gollark: Arch Linux (by the way).
gollark: Depending on how highly efficient™ the company is, that or just replace the entire board.
gollark: Anyway, what do the wise people of this channel think I should do regarding this? I can probably:- ignore the hypothetical capacitor and hope it hypothetically exploding is not important and has not caused/will not cause other damage- send it in for repair under the standard warranty and suffer for some time- upgrade the warranty (fairly cheap) for onsite support, somehow resolve logistical issues surrounding this, and have it maybe get fixed- borrow equipment from somewhere to attempt repairs myself
gollark: The "Ackerman routing protocol" was entirely made up, so yes, that is to be expected.
gollark: (this is over *LAN*; powerline adapters over really bad wiring or something)

See also

References
  1. Cun-Quan Zhang, Integer flows and cycle covers of graphs, Marcel Dekker,1997.
  2. "Handbook in Graph Theory" (2004) ISBN 1-58488-090-2, p. 225
  3. "The Cycle Double Cover Conjecture"
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.