Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old.
Searching relevant literature, I found that the following classes of graphs are known to be reconstructible :
- trees
- disconnected graphs, graphs whose complement is disconnected
- regular graphs
- Maximal Outerplanar Graphs
- maximal planar graphs
- outerplanar graphs
- Critical blocks
- Separable graphs without end vertices
- unicyclic graphs (graphs with one cycle)
- non-trivial cartesian product graphs
- squares of trees
- bidegreed graphs
- unit interval graphs
- threshold graphs
- nearly acyclic graphs (i.e., G-v is acyclic)
- cacti graphs
- graphs for which one of the vertex deleted graph is a forest.
I recently proved that a special case of partial 2-trees are reconstructible. I am wondering if partial 2-trees (a.k.a series-parallel graphs) are known to be reconstructible. Partial 2-trees do not seem to fall into any of the above mentioned categories.
- Am I missing any other known classes of reconstructible graphs in the above list ?
- In particular, are partial 2-trees known to be reconstructible ?
I asked this question at cstheoryquestion at cstheory website also.
