Tutte seminar - Bruce Richter

Friday, July 9, 2010 3:30 pm - 4:30 pm EDT (GMT -04:00)

Long cycles in 2-factors of 3-regular graphs

Speaker: Bruce Richter
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

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.