In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 soc ...
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.
Symbols
A
B
...
, 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 cross ...
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
In graph-theoretic mathematics, a cycle double cover is a collection of cycles in an undirected graph that together include each edge of the graph exactly twice. For instance, for any polyhedral graph, the faces of a convex polyhedron that repre ...
is an open problem in graph theory. The
cycle double cover conjecture
In graph-theoretic mathematics, a cycle double cover is a collection of cycles in an undirected graph that together include each edge of the graph exactly twice. For instance, for any polyhedral graph, the faces of a convex polyhedron that repre ...
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 Theorem, mathematical theorem that characterizes the Edge cycle cover, 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 p ...
* Vertex cycle cover
References
{{reflist
Graph theory objects
Combinatorial optimization