Tutte seminar - Bruce RichterExport this event to calendar

Friday, July 9, 2010 — 3:30 PM to 4:30 PM EDT

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.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
  1. 2019 (160)
    1. November (13)
    2. October (18)
    3. September (15)
    4. August (9)
    5. July (17)
    6. June (18)
    7. May (16)
    8. April (9)
    9. March (24)
    10. February (13)
    11. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)