University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte seminar - Brendan McKayExport this event to calendar

Friday, April 29, 2011 — 3:30 PM to 4:30 PM EDT

Recursive structure of planar graph classes

Speaker: Brendan McKay
Affiliation: Australian National University
Room: Mathematics & Computer Building (MC) 5158

Abstract:

A recursive characterisation of a class of graphs consists of a set of starting graphs in the class, together with a set of operations that modify one graph in the class to form another. It is required that every graph in the class can be obtained from some starting graph by performing a finite sequence of operations. Recursive characterisations can be used to prove properties of the graph class by induction, and can also be used to exhaustively generate the class on the computer. 

In this talk we survey previous recursive characterisations of various classes of planar graphs. Then we present two new results. One is the recursive characterisation of simple 5-regular planar graphs, and the other is the recursive characterisation of fullerenes (also known as buckeyballs). The latter are planar cubic graphs with faces of size five and six, and are of considerable importance in chemistry. 
Finally, we describe how these characterisations can be used to achieve exhaustive generation without isomorphs. 

Joint work with Mahdieh Hasheminezhad, Herbert Fleischner, and Tristan Reeves.

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. 2020 (114)
    1. December (1)
    2. November (11)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (136)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)