(m,n)cycle covers
Definition: If is a graph, a binary cycle of is a set such that every vertex of the graph has even degree. An cyclecover 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 cyclecovers. 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 cutedge has an cyclecover. A "no" indicates that no graph has an cyclecover. A more detailed explanation of the entries in this chart appears below it.
m  
n 

We did not include odd values of n, since any graph with an cyclecover for an odd integer must be Eulerian. The entry "NZ 4flow" is short for nowherezero 4flow. Thus, our chart indicates that ( has a nowherezero 4flow) if and only if ( has a cyclecover) if and only if ( has a cyclecover). 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 BF conjecture is the BergeFulkerson conjecture. In both of these cases, the conjecture is equivalent to the assertion that every graph with no cutedge has an cyclecover (i.e. it would be accurate to put a "yes" in the corresponding. box). For emphasis, we state the BergeFulkerson conjecture again below in this new form.
The fact that the above conjecture is equivalent to the usual statement of the BergeFulkerson conjecture was discovered by Jaeger [J]. For cubic graphs this equivalence is easy to see, since satisfy the BergeFulkerson conjecture if and only if is a cyclecover. By Jaeger's argument, the weak BergeFulkerson conjecture is equivalent to the statement that there exists a fixed integer so that every bridgeless graph has a cyclecover.
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 cyclecover 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 cyclecovers.
Next we turn our attention to orientable cycle covers. If is a directed graph a map is a 2flow 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 2flow is always a cycle. Furthermore, for any oriented cycle, there is a list of edgedisjoint 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 edgedisjoint union of oriented circuits. For an even integer , a orientedcyclecover 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 orientedcyclecovers. We sumarize some of what is known for small values of and below.
m  
n 

Every graph with an cyclecover also has a orientedcyclecover obtained by taking two copies of each cycle with opposite orientations. Thus, by Bermond, Jackson, and Jaeger's cyclecover theorem, every bridgeless graph with no has a orientedcyclecover. DeVos and Goddyn have observed that Seymour's 6flow theorem can be used to construct an orientedcyclecover for every bridgeless graph. By combining these, we find that for every even integer there exists an so that every bridgeless graph has an orientedcyclecover. 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 BergeFulkerson conjecture. To see this analogy, note that ( has a nowherezero 4flow) if and only if ( has a cyclecover) if and only if ( has a orientedcyclecover). The BergeFulkerson conjecture and the above conjecture assert respectively that every bridgeless graph has a cyclecover and a orientedcyclecover (i.e. a cover with double the parameters which are equivalent to a nowherezero 4flow). As with most of the conjectures in this area, the above conjecture is trivially true for graphs with nowherezero 4flows and it holds for the Petersen graph.
Bibliography
[A] D. Archdeacon, Face coloring of embedded graphs. J. Graph Theory, 8(1984), 387398.
[BJJ] J.C. Bermond, B. Jackson, and F. Jaeger, Shortest covering of graphs with cycles, J. Combinatorial Theory Ser. B 35 (1983), 297308. MathSciNet
*[C] A. U. Celmins, On cubic graphs that do not have an edge3colouring, Ph.D. Thesis, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada, 1984.
[F] G. Fan, Integer flows and cycle covers, J. Combinatorial Theory Ser. B 54 (1992), 113122. MathSciNet
[J] F. Jaeger, Flows and Generalized Coloring Theorems in Graphs, J. Combinatorial Theory Ser. B 26 (1979) 205216. MathSciNet
[J88] F. Jaeger, Nowhere zero flow problems. Selected Topics in Graph Theory 3 (L.W.Beineke and R.J.Wilson eds.), Academic Press, London (1988), 7195.
*[P] M. Preissmann, Sur les colorations des arêtes des graphes cubiques, Thèse de 3ème cycle, Grenoble (1981) .
[T54] W.T. Tutte, A Contribution on the Theory of Chromatic Polynomials, Canad. J. Math. 6 (1954) 8091. MathSciNet
[T66] W.T. Tutte, On the Algebraic Theory of Graph Colorings, J. Combinatorial Theory 1 (1966) 1550. MathSciNet
* indicates original appearance(s) of problem.