Long cycles in 2-factors of 3-regular graphs
|Affiliation:||University of Waterloo|
|Room:||Mathematics & Computer Building (MC) 5158|
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.
Joint work with André Kundgen.
200 University Avenue West
Waterloo, ON N2L 3G1