8
$\begingroup$

The Graph Reconstruction Conjecture claims that any simple graph with 3 or more vertices is reconstructible from its "deck" of vertex-deleted subgraphs. (A nice introduction to this problem is at this Wikipedia page.)

My general question: I would be interested in any recent progress on the conjecture. The sources in the Wikipedia article seem to be quite old. (I also have a copy of a Bondy and Hemminger survey from 1977. A more recent article by Ramachandran (in pdf here) is from 2004 but like many works on this conjecture, quickly detours into other reconstruction questions, edge reconstruction, etc.)

A more specific question: since one can reconstruct the degree sequence of a graph then any regular graph can be reconstructed. But graphs with exactly two degrees, $k$ and $k-1$, seem to be quite hard to reconstruct. I would be especially interested in results related to graphs with exactly two degrees, $k$ and $k-1.$

Even more narrowly, can we reconstruct graphs in which all vertices have degree 2 or 3? (Apparently Kocay worked on that in the early 1980s, says Ramachandran.) Surely "small" graphs of degrees {2,3} are accessible to modern computers so there may now be a place for fertile exploration on this problem?

Improve this question
$\endgroup$
3
  • $\begingroup$ Do we know the number of vertices with degree $2$ and $3$? Recently, Adryan Bondy(I think) published a survey about open problems in graph theory. The first problem is about this conjecture. But this is very interesting problem. $\endgroup$
    – Shahrooz
    Commented Dec 18, 2011 at 9:58
  • $\begingroup$ The whole degree sequence can be determined from the deck. $\endgroup$
    – Brendan McKay
    Commented Dec 18, 2011 at 15:02
  • $\begingroup$ I do not think there has been much (any?) recent progress. Asking Bill Kocay would be a good idea. $\endgroup$
    – Chris Godsil
    Commented Dec 18, 2011 at 15:50

5 Answers 5

Reset to default
1
$\begingroup$

I have a paper on the Reconstruction Conjecture. It was published in an Elsevier journal dedicated to Discrete Mathematics. Its available online since 2007:

Kia Dalili, Sara Faridi and Will Traves. Note: The Reconstruction Conjecture and edge ideals. Discrete Mathematics 308(10), pp. 2002–2010, 2008. (MathSciNet review)

Just type Kia Dalili in the Author field for Search and it will show up.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. (The reconstruction conjecture and edge ideals, Dalili, et. al. Discrete Mathematics (Elsevier) v. 308, no. 10 (2008-01-01) p. 2002-2010. ISSN: 0012-365X.) I found a pdf by searching on the title. $\endgroup$
    – Ken W. Smith
    Commented Dec 18, 2011 at 14:01
5
$\begingroup$

Not many people work on the classical reconstruction conjecture these days, probably because only very difficult subproblems remain. The only recent good result I am aware of is this one by Brignall, Georgiou, and Waters.

About degrees 2 and 3, it could be tested by computer up to about 22 vertices. Would that be useful?

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ I have come to suspect that the reconstruction conjecture is "true by accident" and therefore likely to be impossible to prove. In other words, the "chances" (not using the word rigorously) of having two non-isomorphic graphs with isomorphic decks is vanishingly small but there's no particular reason for them not to. $\endgroup$
    – Gordon Royle
    Commented Dec 18, 2011 at 2:13
  • $\begingroup$ Yes, I think a computer search on degrees 2 and 3 would be very useful. (What's the best way to do this? I think I have an old version of Nauty installed on my Mac but it has been a while since I used it -- sorry!) Graphs with degrees 2 & 3 would be (roughly) identified by the vertices of degree 3. "Smooth out" the vertices of degree 2, replacing edge-vertex-edge by a single edge, and one has a cubic graph. Can we reconstruct that cubic graph? $\endgroup$
    – Ken W. Smith
    Commented Dec 18, 2011 at 13:35
  • $\begingroup$ I still have the programs I used to prove the reconstruction conjecture for various small graphs in the early 1990s. I'll dust them off and see if they still run. I'll also see how far I can get with degrees 3 and 4. $\endgroup$
    – Brendan McKay
    Commented Dec 18, 2011 at 15:01
0
$\begingroup$

This seems to be a little more recent that 1977:

http://www.akcejournal.org/contents/vol1no1/Vol_1no_1-6.pdf

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ That's the survey article by Ramachandran from 2004. (I couldn't find any other relevant ones from this century.) $\endgroup$
    – Ken W. Smith
    Commented Dec 17, 2011 at 17:07
  • $\begingroup$ Oops, I didn't notice you had already mentioned it... $\endgroup$
    – Igor Rivin
    Commented Dec 17, 2011 at 22:13
0
$\begingroup$

Some recent papers of mine settle some new cases of the graph reconstruction conjecture. Recall that a limb of a graph $G$ is a maximal subtree, and the trunk is $G$ with $L-r$ removed for each limb $L$ with root $r$ (or empty if is $G$ a tree). It has long been known that the limbs and trunk are reconstructible, $G$ is reconstructible if it is a tree, and $G$ is reconstructible if it has no limbs and the trunk has more than one block.

In "Strong Reconstructibility of the Block-Cutpoint Tree" it is shown that $G$ is reconstructible if it is not a "single block trunk" graph, i.e., its trunk has a single block.

Let $p$ be the number of edges minus the number of nodes. In "Two Cases of Reconstruction of Separable Graphs" it is shown that a single block trunk graph is reconstructible if $p=0$ or $p=1$.

In "Some Results on Reconstructibility of Colored Graphs" the following are shown. A graph which is not a single block trunk graph, with a vertex and edge coloring, is reconstructible. A block with vertex colors is reconstructible if $0\leq p\leq 2$. Edge colored versions of $K_5$ are not reconstructible, refuting a 1970 conjecture of B. Manvel.

It has yet to be detemined if single block trunk graphs with $p=2$ are reconstructible.

Improve this answer
$\endgroup$
0
$\begingroup$

The edge-reconstruction of graphs with degrees k and k-1 has been proved, in 2984 I think, by Ellingham, Myrvold and Hoffman. You can find it in J Graph Theory Vol 11. It is a very clever proof and it's difficulty indicates how much more difficult it is to obtain vertex-reconstruction. Even the vertex-reconstruction of graphs with degrees 2 and 3 is one very tantalising problem because it looks so easy but it is not.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .