14
$\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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Very nice question, I would assume someone has studied relations between reconstruction and treewidth. $\endgroup$
    – Gjergji Zaimi
    Commented Feb 27, 2011 at 21:05
  • $\begingroup$ @Shiva, can you please tell me which of the proofs used algebraic graph theory? The answer may come here: mathoverflow.net/questions/34914/… $\endgroup$
    – Unknown
    Commented Feb 27, 2011 at 22:51
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Feb 27, 2011 at 23:52
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Feb 27, 2011 at 23:54
  • $\begingroup$ $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. $\endgroup$
    – Gordon Royle
    Commented Feb 21, 2014 at 2:01

0

Reset to default

You must log in to answer this question.