All the King's Horses
| Speaker: | Chris Godsil |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
A vertex-deleted subgraph of G is a graph we get from G by deleting a single vertex. The famous vertex-reconstruction conjecture, due to Ulam asserts that if |V(G)|>2 and we know the isomorphism class of each vertex-deleted subgraph of G, we can reconstruct the graph G. This is one of the oldest open problems in graph theory.
The
title
of
this
talk
is
the
title
of
a
paper
of
Tutte's
where
he
proved
two
interesting
results
about
this
conjecture.
First
he
showed
that
if
given
the
isomorphism
class
of
each
vertex-deleted
subgraph,
it
is
possible
to
determine
the
Tutte
polynomial
of
G.
He
also
proved
that
if
the
characteristic
polynomial
of
the
adjacency
matrix
of
G
is
irreducible
over
the
rationals,
then
G
is
reconstructible.
I
will
discuss
the
proofs
of
these
results
and
some
related
history.
(This
talk
is
part
of
a
series
of
talks
dedicated
to
honouring
the
10th
anniversary
of
Bill
Tutte's
passing).