Reconstruction Conjecture and Partial 2-trees

Question

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: http://www.springerlink.com/content/p6r03877310411wr/ claims that N-free ordered sets are reconstructible. — mhum, Feb 27 '11 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. — András Salamon, Feb 28 '11 at 09:15
For your list: Kiyomi, Saitoh, and Uehara showed that Bipartite Permutation Graphs Are Reconstructible. — Yota Otachi, Mar 02 '11 at 03:41
One more for your list: some planar graphs are reconstructible. — virgi, Mar 13 '11 at 21:14

score 4 · Answer 1 · answered Sep 04 '12 at 23:53

I believe that it has not been shown that bidegreed graphs are reconstructible. Bidegreed graphs are edge-reconstructible. Kocay did some work on reconstruction of bidegreed graphs, but did not reach a comprehensive result that I have been able to find. The notion that it has been proven that bidegreed graphs are reconstructible seems to be a bit of misinformation circulating on the web.

Reconstruction Conjecture and Partial 2-trees

1 Answers1

Linked