All the King's Horses
|Affiliation:||University of Waterloo|
|Room:||Mathematics & Computer Building (MC) 5158|
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).
200 University Avenue West
Waterloo, ON N2L 3G1