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.

  • 4
    This might be a good question to ask at mathoverflow, mathoverflow.net , with a [reference-request] tag in addition to the [graph-theory] tag. – Arturo Magidin Feb 27 '11 at 4:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.