|
Friday, July 9, 2010 |
|
|
|
|
Long cycles in 2-factors of 3-regular graphs |
|
|
Petersen's Theorem says that every 2-connected, 3-regular graph has a 2-factor
(i.e., a set of disjoint cycles whose union contains all the vertices). We are
interested in finding the longest cycle that occurs in a 2-factor of such a
graph. (For example, the Petersen graph, there is a cycle of length 9, but it is
not in any 2-factor. The longest cycle in a 2-factor of the Petersen graph has
length 5.) We prove that there are arbitrarily large 3-connected, 3-regular
graphs with no 2-factor having a cycle of length more than 16 and that every
2-connected, 3-regular graph with at least 12 vertices has a 2-factor having a
cycle of length at least 7. Obviously, lots of natural questions remain. |