|
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)
|