Title: Modular Decomposition and Graph Reconstruction
The Reconstruction Conjecture, one of the most well-known open problems
in Combinatorics, dates back to Kelly in 1957. It states that every graph
on at least 3 vertices can be determined uniquely by its multiset of
vertex-deleted subgraphs.
An easy argument using the concept of "attributability" proves that
disconnected graphs (and graphs whose complements are disconnected) can
be reconstructed. One natural generalisation of connectedness is to
consider decomposing a graph into its k-connected components, but the
attributability argument fails here when trying to "glue" these components
back together. However, there are other ways to decompose a graph, and one
which has proved particularly useful in a wide range of contexts is the
"modular decomposition", which uniquely describes a graph in terms of smaller
"indecomposable" (or prime) graphs. In this talk, I will describe how the
attributability argument can be adapted to prove that many graphs which have
non-trivial modular decompositions (i.e. are not prime) can be reconstructed.
Joint work with: Nic Georgiou and Rob Waters.