13
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.