Fast Generation of Cubic Graphs, Snarks and Fullerenes
Jan Goedgebeur (CECS)
COMPUTER SCIENCE SEMINARDATE: 2011-06-16
TIME: 16:00:00 - 17:00:00
LOCATION: CSIT Seminar Room, N101
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
Cubic or 3-regular graphs are a very important graph family since they have various applications in mathematics and chemistry. We will present a new algorithm for the efficient generation of all non-isomorphic cubic graphs. We will describe how the graphs are constructed one by one while at the same time avoiding isomorphic copies. And we are going to provide details on how to efficiently implement these methods for simple cubic graphs.
We will also show how this algorithm can be extended for the efficient generation of all non-isomorphic snarks. A snark is a simple, cyclically 4-edge connected cubic graph with girth at least 4 and chromatic index 4 (i.e. the edges cannot be coloured with 3 colours). Snarks are of interest since for a lot of interesting open conjectures it can be proven that if the conjecture is false, the smallest possible counterexamples will be snarks. Our implementation of this algorithm to generate snarks is roughly 30 times faster than former generators for snarks. Using this generator we were able to generate all snarks up to 34 vertices, which was impossible with previous methods. With this new list of snarks we were able to find counterexamples for several published open conjectures.
We will conclude this talk with the presentation of a completely different algorithm for the generation of the Nobel Prize winning fullerenes. These are cubic planar graphs where all faces are either pentagons or hexagons.
This is joint work with Gunnar Brinkmann and Brendan McKay.
BIO:
Jan is a PhD student from the University of Ghent visiting the Algorithms & Data group for six months
