Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
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: mathoverflow.net/questions/34914/… –  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 at 2:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.