TOPICS
Search

Cycle Double Cover Conjecture


The cycle double cover conjecture states that every bridgeless graph has a collection of cycles which together contain every edge exactly twice. This conjecture remains open, and was independently formulated by Szekeres (1973) and Seymour (1979).

A dual form of the problem is called the Fulkerson conjecture.


See also

Bridgeless Graph, Cycle Double Cover, Fulkerson Conjecture, Hamiltonian Graph

Explore with Wolfram|Alpha

References

Archdeacon, D. "The Cycle Double Cover Conjecture." http://www.cems.uvm.edu/~archdeac/problems/cyclecov.htm.Goddyn, L. "Cycle Covers of Graphs." Ph.D. thesis. Waterloo, Ontario, Canada: University of Waterloo.Jaeger, F. "A Survey of the Cycle Double Cover Conjecture." In Cycles in Graphs (Ed. B. Alspach and C. D. Alspach). North Holland, pp. 1-12, 1985.Seymour, P. D. "Sums of Circuits." In Graph Theory and Related Topics (Ed. J. A. Bondy and U. R. S. Murty). New York: Academic Press, pp. 341-355, 1979.Szekeres, G. "Polyhedral Decompositions of Cubic Graphs." Bull. Austral. Math. Soc. 8, 367-387, 1973.West, D. "Cycle Double Cover Conjecture (1978/1979)." http://www.math.uiuc.edu/~west/openp/cdc.html.

Referenced on Wolfram|Alpha

Cycle Double Cover Conjecture

Cite this as:

Weisstein, Eric W. "Cycle Double Cover Conjecture." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CycleDoubleCoverConjecture.html

Subject classifications