Tommy R. Jensen, The Cycle Double Cover Problem for graphs

The Cycle Double Cover Problem for graphs
Tommy R. Jensen
Department of Mathematics, Kyungpook National University, Daegu, Korea
2009/04/24 Friday 4PM-5PM

The Cycle Double Cover Problem in Graph Theory suggests that all 2-connected graphs share a certain property with 2-connected planar maps. Such a map clearly contains a collection of cycles, indeed the boundary cycles of its faces, such that each edge belongs to exactly
two of them. The generalization of this property to nonplanar graphs remains one of the central open problems in Graph Theory.

We investigate this problem by generalizing a suitable variation of the statement of another almost obvious property of planar maps, namely the Jordan Curve Theorem. The generalization suggests a new conjecture which is much stronger than the Cycle Double Cover Conjecture. In fact it would imply a very strong form of the Cycle Double Cover Conjecture, suggesting that every cycle in a 2-connected graph appears in at least one cycle double cover of the graph.

We prove the stronger conjecture in a few important special cases.


Comments are closed.