The cycle double cover conjecture for bridgeless graphs
The cycle double cover conjecture for bridgeless graphs
Let be a graph. A cycle double cover is a collection of cycles such that every edge of lies in exactly two cycles. For a cubic graph, this is equivalent to requiring that exactly three cycles pass through each node. A simplicial surface has as its face graph when its faces correspond to the vertices and edges of in the usual incidence structure.
Cycle double cover conjecture. Every cubic graph containing no bridges has a cycle double cover, or equivalently is the face graph of a simplicial surface. More generally, every bridgeless graph admits a cycle double cover.
The conjecture would characterize which bridgeless cubic graphs arise as face graphs of simplicial surfaces and remains open: it is not known whether all cubic bridgeless graphs admit a cycle double cover.
Equivalent formulations 1
Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.
The cycle double cover conjecture for bridgeless graphs
A graph is bridgeless if it has no bridges, meaning no edge whose deletion increases the number of connected components. A cycle double cover is a family of cycles such that every edge of the graph belongs to exactly two members of the family.
Cycle double cover conjecture. Every bridgeless graph has a cycle double cover.
This is a major open problem in graph theory. The conjecture is known in several special cases, but remains unresolved for general bridgeless graphs.
source: Delio Mugnolo and Marvin Plümer, “Lower Estimates on Eigenvalues of Quantum Graphs”, arXiv:1907.13350 (2020).
Sources & referencesView supporting material
Primary source
Reymond Akpanya and Tom Goertzen, “Surfaces with given Automorphism Group”, arXiv:2307.12681 (2023).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.