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.

  • 1
    Very nice question, I would assume someone has studied relations between reconstruction and treewidth. – Gjergji Zaimi Feb 27 '11 at 21:05
  • @Shiva, can you please tell me which of the proofs used algebraic graph theory? The answer may come here:… – Unknown Feb 27 '11 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 – Gerhard Paseman Feb 27 '11 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 – Gerhard Paseman Feb 27 '11 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. – Gordon Royle Feb 21 '14 at 2:01

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.