[Mathclub-members] Wednesday 9-23: Reconstruction of a family of Separable Graphs

[Hannah R Kolb]

Reconstruction of a family of Separable Graphs
Hannah Kolb

This talk is geared towards undergraduates- even if you haven't taken any Graph
Theory!

When: Wednesday 9/23/09
Where: E1 (room TBA)
Hosted by IIT Math Club
*There will be pizza

Abstract:
In the 1950's, Ulam and Kelly posed the reconstruction conjecture in graph
theory: every graph with n>2 vertices is uniquely determined by its collection
of vertex-deleted subgraphs.  While the problem remains open, many families of
graphs have been shown to be reconstructible, such as disconnected graphs,
regular graphs, and trees.  In 1976, Manvel proved that graphs with connectivity
1 and no leaves are reconstructible.  Here, we prove the reconstructibility of
graphs with connectivity 1 where no maximal end tree is a leaf.