<p>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.</p>

CC BY-SA 4.0
2024-12-18T11:47:01.510Z
The confusion comes from : bi-degreed graph are **edge**-reconstructible.
Jérôme JEAN-CHARLES
CC BY-SA 3.0
2012-09-04T23:53:11.840Z
2012-09-04T23:53:11.840Z
MattM
<p><a href="http://garden.irmacs.sfu.ca/?q=op/reconstruction_conjecture" rel="noreferrer">Reconstruction conjecture</a> says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old.</p>

<p>Searching relevant literature, I found that the following classes of graphs are known to be reconstructible :</p>

<ul>
<li>trees</li>
<li>disconnected graphs, graphs whose complement is disconnected</li>
<li>regular graphs</li>
<li>Maximal Outerplanar Graphs</li>
<li>maximal planar graphs</li>
<li>outerplanar graphs</li>
<li>Critical blocks</li>
<li>Separable graphs without end vertices</li>
<li>unicyclic graphs (graphs with one cycle)</li>
<li>non-trivial cartesian product graphs</li>
<li>squares of trees</li>
<li>bidegreed graphs</li>
<li>unit interval graphs</li>
<li>threshold graphs</li>
<li>nearly acyclic graphs (i.e., G-v is acyclic)</li>
<li>cacti graphs</li>
<li>graphs for which one of the vertex deleted graph is a forest.</li>
</ul>

<p>I recently proved that a <em>special case</em> of partial 2-trees are reconstructible. I am wondering if partial 2-trees (a.k.a <a href="http://en.wikipedia.org/wiki/Series-parallel_graph" rel="noreferrer">series-parallel graphs</a>) are known to be reconstructible. Partial 2-trees do not seem to fall into any of the above mentioned categories.</p>

<ul>
<li>Am I missing any other known classes of reconstructible graphs in the above list ?</li>
<li>In particular, are partial 2-trees known to be reconstructible ?</li>
</ul>

CC BY-SA 2.5
2011-03-13T21:14:56.830Z
One more for your list: [some planar graphs are reconstructible](http://portal.acm.org/citation.cfm?id=1279202).
virgi
CC BY-SA 3.0
2012-02-21T11:53:48.333Z
Shiva, Did you get any new result?
Saeed
CC BY-SA 2.5
2011-02-27T23:37:46.243Z
I don't have access to it, but this paper: http://www.springerlink.com/content/p6r03877310411wr/ claims that N-free ordered sets are reconstructible.
mhum
CC BY-SA 2.5
2011-02-28T09:15:57.737Z
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.
András Salamon
CC BY-SA 2.5
2011-03-02T03:41:31.807Z
For your list: Kiyomi, Saitoh, and Uehara showed that [Bipartite Permutation Graphs Are Reconstructible](http://dx.doi.org/10.1007/978-3-642-17461-2_29).
Yota Otachi
<reference-request><graph-theory><co.combinatorics><treewidth>
Reconstruction Conjecture and Partial 2-trees
Shiva Kintali
# Reconstruction Conjecture and Partial 2-trees

(Asked by: username_0 on 2011-02-26)

[Reconstruction conjecture](http://garden.irmacs.sfu.ca/?q=op/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](http://en.wikipedia.org/wiki/Series-parallel_graph)) 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 ?

**Tags:** reference-request, graph-theory, co.combinatorics, treewidth
> **Comments:**
> **username_3**: I don't have access to it, but this paper: http://www.springerlink.com/content/p6r03877310411wr/ claims that N-free ordered sets are reconstructible.  
> **username_4**: 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.  
> **username_5**: For your list: Kiyomi, Saitoh, and Uehara showed that [Bipartite Permutation Graphs Are Reconstructible](http://dx.doi.org/10.1007/978-3-642-17461-2_29).  
> **username_1**: One more for your list: [some planar graphs are reconstructible](http://portal.acm.org/citation.cfm?id=1279202).  
> **username_2**: Shiva, Did you get any new result?  

---

## 1 answers

### Answer by username_6 on 2012-09-04. Score: 4

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.

> **Comments:**
> **username_7**: The confusion comes from : bi-degreed graph are **edge**-reconstructible.  

---

