Home » Subject » Graph Theory » Basic G.T. » Cycles

Bigger cycles in cubic graphs (Solved)

Importance: Medium ✭✭
Author(s):
Subject: Graph Theory
» Basic Graph Theory
» » Cycles
Keywords: cubic
cycle
Recomm. for undergrads: no
Posted by: mdevos
on: August 31st, 2007
Solved by: See Stable dominating circuits in snarks" (Discrete Math 233 (247-256) 2001) by Martin Kochhol
Problem   Let $ G $ be a cyclically 4-edge-connected cubic graph and let $ C $ be a cycle of $ G $. Must there exist a cycle $ C' \neq C $ so that $ V(C) \subseteq V(C') $?

The main interest in this problem is that an affirmative solution would imply the Cycle double cover conjecture. The idea behind this is an old one - probably due to Seymour - which shall be described below. I (M. DeVos) regard this problem as folklore, which is why I haven't listed an author.

One sensible approach to the cycle double cover conjecture is that described in Faithful cycle covers. Quickly, the idea here is to consider a more general problem.. given a graph $ G $ and a map $ p : E(G) \rightarrow {\mathbb Z} $, say that a list of cycles of $ G $ is a $ p $-cover if every edge $ e $ appears in exactly $ p(e) $ cycles from the list. Now, we are interested in what properties guarantee the existence of a $ p $-cover. The Cycle double cover conjecture asserts that a $ p $-cover exists whenever $ G $ is bridgeless and $ p $ is constantly 2. Another interesting special case is when $ G $ is a bridgeless cubic graph, the range of $ p $ is a subset of $ \{1,2\} $, and $ p^{-1}(1) $ is a union of (edge sets of) cycles. It might be tempting to hope that under these assumptions a $ p $-cover would always exist, but this is false.. if $ G $ is the Petersen graph and $ p $ has weight 2 on a perfect matching and 1 elsewhere, then there is no $ p $-cover. In this weighting, the edges of weight 1 form two cycles. The following conjecture asserts that no such example exists if the edges of weight 1 form a single cycle.

Conjecture   Let $ G $ be a bridgeless cubic graph, let $ p : E(G) \rightarrow \{1,2\} $ and assume that $ p^{-1}(1) $ is a cycle $ C $. Then there exists a $ p $-cover of $ G $.

This conjecture is equivalent to the assertion that for every bridgeless cubic graph $ G $ and every cycle $ C $ of $ G $, there exists a cycle double cover of $ G $ using $ C $. So, in particular, it implies the cycle double cover conjecture. An affirmative solution to the main problem on this page would imply this conjecture (and thus cycle double cover). Let us ignore the details about edge connectivity (the ideas here are standard - and easy to find) and state the main idea behind this implication. The trick is to proceed by induction (say on $ \sum_{e \in E(G)} p(e) $), then choose a cycle $ C' \neq C $ so that $ V(C) \subseteq V(C') $, and consider $ D = E(C) \triangle E(C') $ (symmetric difference). Note that $ D $ is a union of cycles (which we will eventually use in our cover). Next, modify $ p $ and $ G $ to form $ p' $ and $ G' $ by decreasing the weight of every edge in $ D $ and then deleting edges of weight 0. An easy check shows that $ G' $ is a subdivision of a bridgeless cubic graph, and $ p' $ is a weight function on $ G' $ which has weight 1 on $ E(C') $. So, by induction, we find a $ p' $-cover of $ G' $. Now adding back the cycles formed by $ D $ gives us a $ p $-cover of $ G $.

Although the problem looks a bit greedy, it is true in a number of special cases. First off, if $ C $ is a Hamiltonian cycle of $ G $, then Smith's theorem shows that $ G $ has another Hamiltonian cycle $ C' $ (which obviously satisfies the condition $ V(C) \subseteq V(C') $). A somewhat more subtle application of the same theorem shows that the problem also has an affirmative answer when $ |V(G) \setminus V(C)| = 1 $. If we drop the assumption of cyclic 4-edge-connectivity, there is a counterexample $ G,C $ where $ |V(G) \setminus V(C)| = 2 $ which is based on gluing two Petersen graphs together at a vertex. However, as far as we know, the only such examples have nontrivial 3-edge-cuts.

Related problems

Cycle double cover conjecture
Faithful cycle covers
add new comment

This conjecture is false

On September 4th, 2009 Anonymous says:

In the paper "Stable dominating circuits in snarks" (Discrete Math 233 (247-256) 2001) Martin Kochhol gives a counter example to this conjecture (in fact he gives an infinite family of them).

Using computer search I have found even smaller counter examples (the smallest has just 20 vertices).

Best regards,

Jonas Hägglund

reply

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.