(8,4)-Directed-Cycle Covers

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