Modular Decomposition and Graph Reconstruction part 2

From A = B to Z = 60
Conference in Honor of Doron Zeilberger's 60th Birthday
May 27 - 28, 2010. Rutgers University.

Robert Brignall, University of Bristol, UK
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.

Category:

Education

Tags:

• RUTGERS
• EXPERIMENTAL
• MATHEMATICS
• SEMINAR