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, Amsterdam, 1990.

[F2] H. Fleischner, “Eulerian graphs and related topics Vol 2”, Ann. Discrete Math 50, North-Holland, Amsterdam, 1991.

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of VermontBurlington VT 05405 USA.

Send comments to dan.archdeacon@uvm.edu

December 2003