Open Problem Garden

Definition: Let be a graph and let . A list of cycles of is a faithful (cycle) cover of if every edge of occurs in exactly cycles of . Thus, the cycle double cover conjecture is equivalent to the statement that has a faithful cover for every graph with no bridge. We define the map to be admissable if satisfies the following properties:

i is nonnegative.

ii is even for every edge-cut .

iii for every edge-cut and edge .

It is easy to see that has a faithful cover only if is admissable. However, the converse is false. A counterexample is obtained by taking the Petersen graph, putting weight on the edges of a perfect matching, and elsewhere.

More generally, for a graph G=(V,E), one may consider the vector space of real numbers indexed by E. We associate every circuit C with its incidence vector. Most of the basic questions about this space are solved. Seymour [S] has shown that a vector p can be written as a nonnegative rational combination of cycles if and only if it satisfies conditions (i) and (iii) in the definition of admissable. It is an easy exercise to show that for a 3-edge-connected graph G, a vector p can be written as an integer combination of cycles if and only if p satisfies (ii) in the definition of admissable. Seymour's conjecture is equivalent to the statement that every admissable map may be realized as a half-integer combination of circuits. Note the similarity of this to The Berge-Fulkerson conjecture.

The most interesting result about faithful covers is a theorem of Alspach, Goddyn, and Zhang which resolved a conjecture of Seymour. They prove that whenever has no minor isomorphic to Petersen, every admissable map has a corresponding faithful cover. For a general graph with no bridge, Bermond, Jackson, and Jaeger [BJJ] proved that has a faithful cover and Fan [F] proveed that has a faithful cover. DeVos, Johnson, and Seymour [DJS] proved that has a faithful cover whenever is admissable and there is a nonnegative integer such that holds for every edge . However, little else seems to be known. In particular, it does not appear to be known if there exist integers with arbitrarily large so that has a faithful cover whenever is an admissable function taking on only the values . Such a result would appear to require an idea not contained in any of the aforementioned papers.

The analogous problem for oriented circuit covers does not appear to be very promising. It is easy to see that for an orientation of a series parallel graph G and a map which satisfies the obvious conditions, that will have a circuit cover using every edge in its given direction. However, even with a minor, there is a great deal of forcing, and nothing much looks like it would be true.