Sabidusi’s Compatibility
Conjecture
A cycle in a graph is
a simple closed walk. The following is known as Sabidusi’s
Compatibility Conjecture.
Conjecture: Given an Eulerian
trail T in a graph G,
there exists a partition of the edges of G
into cycles such that consecutive edges in T lie in different cycles.
The conjecture, if true, implies the cycle double cover conjecture. See [F1] and [F2] for details on this relation.
The following Faithful Decomposition Conjecture is more general.
Conjecture: Let G be a 6-edge-connected Eulerian graph and let P_1 be any partition of the edges of G into cycles. Then there exists a partition P_2 of the edges of G into cycles such that no pair of edges are consecutative in both P_1 and P_2.
The requirement of 6-edge-connected is necessary, as seen by the example where edges in a perfect matching of the Petersen Graph are doubled and the partition P_1 of the resulting graph has five 2-cycles and two 5-cycles.
References:
[F1] H. Fleischner,
“Eulerian graphs and related topics Vol 1”, Ann. Discrete Math 45, North-Holland,
[F2] H. Fleischner,
“Eulerian graphs and related topics Vol 2”, Ann. Discrete Math 50, North-Holland,
Submitted
by: Dan Archdeacon, Department of Mathematics and Statistics,
Send comments to dan.archdeacon@uvm.edu
December 2003