Home » Subject » Graph Theory

Odd cycles and low oddness

Importance: Medium ✭✭
Author(s):
Subject: Graph Theory
Keywords:
Recomm. for undergrads: no
Posted by: Gagik
on: January 15th, 2010
Conjecture   If in a bridgeless cubic graph $ G $ the cycles of any $ 2 $-factor are odd, then $ \omega(G)\leq 2 $, where $ \omega(G) $ denotes the oddness of the graph $ G $, that is, the minimum number of odd cycles in a $ 2 $-factor of $ G $.

add new comment

This conjecture is false.

On June 29th, 2010 Anonymous says:

For odd $ n $ and $ i\in[n] $, let $ H_i $ be the graph obtained by deleting an edge, say $ x_iy_i $, from the Petersen graph. Define $ G_n $ to be the graph obtained by joining vertex $ y_i $ and vertex $ x_{i+1} $ with an edge (with subscripts reduced modulo $ n $). For each $ i\in[n] $, the set $ \{y_{i-1}x_{i},y_ix_{i+1}\} $ is an edge cut. Hence, in any 2-factor of $ G_n $, either none of the edges of the form $ y_ix_{i+1} $ are contained in a cycle, or all of them are contained in the same cycle.

Case 1: If none of the edges described above are contained in a cycle of a 2-factor of $ G_n $, then this 2-factor contains a 2-factor of $ H_i $ for each $ i $. These 2-factors are also 2-factors of the graphs $ H_i+x_iy_i $, that is, each is a 2-factor of the Petersen graph. Each 2-factor of the Petersen graph consists of two cycles of 5 vertices, hence, any such 2-factor of $ G_n $ contains $ 2n $ cycles of odd length.

Case 2: See the comment below.

reply

This conecture is false.

On July 2nd, 2010 Anonymous says:

Case 2: If all of the edges of the form $ y_ix_{i+1} $ are contained in the same cycle in a 2-factor of $ G_n $, then replacing the edges $ y_ix_{i+1} $ with the edges $ x_iy_i $ converts this 2-factor of $ G_n $ into a 2-factor of $ n $ disjoint copies of the Petersen graph. Hence, when restricted to each $ H_i $, the 2-factor of $ G_n $ consists of a cycle with 5 vertices and a $ x_iy_i $-path containing a total of 5 vertices. These paths must be joined together through the edges of the form $ y_ix_{i+1} $ creating a cycle of length 5n. Hence, in this case the 2-factor of $ G_n $ contains $ n $ cycles of length 5 and one cycle of length 5n (which is odd).

Now, $ G_n $ is a bridgeless cubic graph whose 2-factors contain only odd cycles, but no 2-factor of $ G_n $ contains fewer than $ n+1 $ cycles.

reply

what is oddness

On January 16th, 2010 Anonymous says:

The notion of oddness of a graph requires explanation.

reply

Let be a bridgeless cubic

On December 13th, 2011 Anonymous says:

Let $ G $ be a bridgeless cubic graph. The oddness of a 2-factor $ F $ is the number of odd circuits of $ F $. The oddness of $ G $ is the smallest oddness over all 2-factors. For example, a 3-edge-colorable cubic graph has oddness zero and the Petersen graph has oddness two.

reply

Comment viewing options

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