1
$\begingroup$

The cycle double covering conjecture states that every bridgeless graph admits a collection of cycles such that every edge in the graph is contained in exactly two cycles from the collection (allowing repetitions). The counterexample with the smallest number of edges is proved to be cubic. My first question is that whether it is true that such a minimal counterexample has the property that removing every edge yields a bridge. In other words, is it true that if $G$ is a graph with a cycle double covering, then $G\cup e$ also has a cycle double covering, where $e$ is an added edge between two vertices of $G$?

My second question is whether anything is known regarding cycle coverings that cover every edge the same number of times.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

No. In a minimal counterexample of the cycle double cover conjecture, removing an edge creates no bridges. The reason is simple. If such an edge existed, then contracting it would yield a smaller counterexample. In fact it is known that a counterexample to the cycle double cover conjecture with the smallest number of edges is a Snark. For more information I suggest looking at M. Chan's survey on the cycle double cover conjecture.

As for your second question, it is known that every bridgeless graph has a cycle cover which covers every edge precisely $2k$ times for every $k\geq 2$. So in particular there is always a cycle 4-cover. This is all stated with references in the survey I mentioned above.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks Gjergji. So it follows that such a minimal graph $G$ admits a cycle covering so that every edge is covered exactly $2E-2$ times, where $E$ is the number of edges of $G$. Maybe there is a more trivial way of covering a graph with cycles that cover all edges the same number of times? Also do we know for example if there is a quadruple covering (or a number smaller than $2E-2$)? $\endgroup$
    – Hej
    Commented Jun 4, 2012 at 2:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .