MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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 '14 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.