24
$\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 ?
$\endgroup$
  • 2
    $\begingroup$ I don't have access to it, but this paper: springerlink.com/content/p6r03877310411wr claims that N-free ordered sets are reconstructible. $\endgroup$ – mhum Feb 27 '11 at 23:37
  • 2
    $\begingroup$ 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. $\endgroup$ – András Salamon Feb 28 '11 at 9:15
  • $\begingroup$ For your list: Kiyomi, Saitoh, and Uehara showed that Bipartite Permutation Graphs Are Reconstructible. $\endgroup$ – Yota Otachi Mar 2 '11 at 3:41
  • $\begingroup$ One more for your list: some planar graphs are reconstructible. $\endgroup$ – virgi Mar 13 '11 at 21:14
  • 2
    $\begingroup$ Shiva, Did you get any new result? $\endgroup$ – Saeed Feb 21 '12 at 11:53
4
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.