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 ?
Improve this question
$\endgroup$
5
  • 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, 2011 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, 2011 at 9:15
  • $\begingroup$ For your list: Kiyomi, Saitoh, and Uehara showed that Bipartite Permutation Graphs Are Reconstructible. $\endgroup$
    – Yota Otachi
    Mar 2, 2011 at 3:41
  • $\begingroup$ One more for your list: some planar graphs are reconstructible. $\endgroup$
    – virgi
    Mar 13, 2011 at 21:14
  • 2
    $\begingroup$ Shiva, Did you get any new result? $\endgroup$
    – Saeed
    Feb 21, 2012 at 11:53

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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