# 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 asked this question at cstheory website also.

• Very nice question, I would assume someone has studied relations between reconstruction and treewidth. Feb 27, 2011 at 21:05
• @Shiva, can you please tell me which of the proofs used algebraic graph theory? The answer may come here: mathoverflow.net/questions/34914/… Feb 27, 2011 at 22:51
• If you gave me a good definition of 2-tree in the post, and a couple not-so-obvious reasons why it doesn't seem to fit in some of the classes on the list, I might be inclined to answer (or at least think about) your question. I am not yet inspired to look up the definition myself and check. Gerhard "Ask Me About System Design" Paseman, 2011.02.27 Feb 27, 2011 at 23:52
• Yes, I see the link to series-parallel graphs, but I still prefer a recap of "partial 2-tree". Gerhard "Ask Me About System Design" Paseman, 2011.02.27 Feb 27, 2011 at 23:54
• $K_2$ is a 2-tree. If $X$ is a 2-tree then so is $X + v$ where $v$ lies in a triangle with 2 vertices of $X$. There are no other 2-trees. A partial 2-tree is a 2-tree with some edges removed. Feb 21, 2014 at 2:01