Definition: If is a graph, a binary cycle of is a set such that every vertex of the graph has even degree. An -cycle-cover of is a list consisting of cycles so that every edge of is contained in exactly of these cycles.

Since every binary cycle can be written as a disjoint union of edge sets of ordinary cycles, the above conjecture is a strengthening of the cycle double cover conjecture. For positive integers it is natural to ask what family of graphs have -cycle-covers. The following chart gives some information about this question for small values of and . A "yes" in the box indicates that every graph with no cut-edge has an -cycle-cover. A "no" indicates that no graph has an -cycle-cover. A more detailed explanation of the entries in this chart appears below it.

We did not include odd values of n, since any graph with an -cycle-cover for an odd integer must be Eulerian. The entry "NZ 4-flow" is short for nowhere-zero 4-flow. Thus, our chart indicates that ( has a nowhere-zero 4-flow) if and only if ( has a -cycle-cover) if and only if ( has a -cycle-cover). These equivalences were discovered by Tutte [Tu].

Two of the boxes are conjectures. The 5CDC conj is the 5 cycle double cover conjecture and the B-F conjecture is the Berge-Fulkerson conjecture. In both of these cases, the conjecture is equivalent to the assertion that every graph with no cut-edge has an -cycle-cover (i.e. it would be accurate to put a "yes" in the corresponding. box). For emphasis, we state the Berge-Fulkerson conjecture again below in this new form.

The fact that the above conjecture is equivalent to the usual statement of the Berge-Fulkerson conjecture was discovered by Jaeger [J]. For cubic graphs this equivalence is easy to see, since satisfy the Berge-Fulkerson conjecture if and only if is a -cycle-cover. By Jaeger's argument, the weak Berge-Fulkerson conjecture is equivalent to the statement that there exists a fixed integer so that every bridgeless graph has a -cycle-cover.

A postman set is a set of edges such that is a cycle. The entry "k post. sets" in the box of the above chart indicates that a graph G has a -cycle-cover if and only if it is possible to partition the edges of into postman sets. This equivalence follows immediately from the definition. Rizzi's Packing postman sets conjecture is thus equivalent to the following conjecture on cycle-covers.

Conjecture  (the packing postman sets conjecture)   If every odd edge-cut of has size , then has a -cycle-cover.

Next we turn our attention to orientable cycle covers. If is a directed graph a map is a 2-flow or an oriented cycle if at every vertex of , the sum of on the incoming edges is equal to the sum of on the outgoing edges. It is easy to see that the support of a 2-flow is always a cycle. Furthermore, for any oriented cycle, there is a list of edge-disjoint circuits with directions so that an edge is forward (backward) in a circuit of if and only if (). So as in the unoriented case, an oriented cycle may be viewed as the edge-disjoint union of oriented circuits. For an even integer , a -oriented-cycle-cover of a graph is a list of oriented cycles so that every edge of appears as a forward edge times and a backward edge times. The following conjecture is the common generalization of the orientable cycle double cover conjecture and the five cycle double cover conjecture. It is due to Archdeacon and Jaeger.

Considerably less is known about -oriented-cycle-covers. We sumarize some of what is known for small values of and below.

Every graph with an -cycle-cover also has a -oriented-cycle-cover obtained by taking two copies of each cycle with opposite orientations. Thus, by Bermond, Jackson, and Jaeger's -cycle-cover theorem, every bridgeless graph with no has a -oriented-cycle-cover. DeVos and Goddyn have observed that Seymour's 6-flow theorem can be used to construct an -oriented-cycle-cover for every bridgeless graph. By combining these, we find that for every even integer there exists an so that every bridgeless graph has an -oriented-cycle-cover. This question is still open for .

The following conjecture appears in the above chart.

This conjecture may be viewed as a sort of oriented version of the Berge-Fulkerson conjecture. To see this analogy, note that ( has a nowhere-zero 4-flow) if and only if ( has a -cycle-cover) if and only if ( has a -oriented-cycle-cover). The Berge-Fulkerson conjecture and the above conjecture assert respectively that every bridgeless graph has a -cycle-cover and a -oriented-cycle-cover (i.e. a cover with double the parameters which are equivalent to a nowhere-zero 4-flow). As with most of the conjectures in this area, the above conjecture is trivially true for graphs with nowhere-zero 4-flows and it holds for the Petersen graph.