# Reconstruction Conjecture and Partial 2-trees

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 don't have access to it, but this paper: springerlink.com/content/p6r03877310411wr claims that N-free ordered sets are reconstructible.
– mhum
Feb 27, 2011 at 23:37
• To further elaborate on @mhum's comment: series-parallel partial orders are precisely those that are N-free, so the paper is claiming that series-parallel posets are reconstructible. The transitive reductions of series-parallel posets are the series-parallel graphs, but I'm not sure how the reconstruction conjecture interacts with the transitive edges. Feb 28, 2011 at 9:15
• For your list: Kiyomi, Saitoh, and Uehara showed that Bipartite Permutation Graphs Are Reconstructible. Mar 2, 2011 at 3:41
• One more for your list: some planar graphs are reconstructible. Mar 13, 2011 at 21:14
• Shiva, Did you get any new result? Feb 21, 2012 at 11:53