Let G be a bridgeless graph. A directed cycle is a subgraph C of G together with a direction on each edge such that at each vertex of C the indegree is equal to the outdegree. An (m,n)-directed-cycle cover is a set of m directed cycles such that each directed edge is in exactly n/2 of these cycles (the definition only makes sense if n is even). .

Conjecture: Every bridgeless graph has an (8,4)-directed-cycle cover.

For a graph G let D(G) denote the graph formed by replacing each edge in G with two oppositely directed edges. An (m,2)-directed-cycle cover of G is equivalent to partitioning the edges of D(G) into cycles of length at least three. It is unknown if this can be done. It is known thta an (m,n)-directed-cycle cover exists for all n except for 2,4, and 10. For details see (m,n)-cycle-covers 

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

Send comments to dan.archdeacon@uvm.edu

December 2003