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.