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

The standard reconstruction conjecture states that a graph is determined by its deck of vertex-deleted subgraphs.

Question: Have other decks been investigated, finding out that only vertex-deleted subgraphs can do the job? If so: Which property of vertex-deleted subgraphs makes them exceptional?

I have three candidates in mind, others are conceivable. (For the sake of simplicity I consider only simple connected graphs $G$.)

  1. the deck of sub-maximal neighbourhoods: Let the sub-maximal neighbourhood of $v$ be the $v$-rooted graph constructed from $G$ by deleting all vertices with maximal distance from $v$.

  2. the deck of distinguishing neighbourhoods: Let the distinguishing neighbourhood of $v$ be the smallest $n$-neighbourhood of $v$ which distinguishes it from all vertices not conjugate to it ($n$-neighbourhood = the $v$-rooted induced subgraph containing all vertices $w$ with distance $d(v,w) \leq n$).

  3. the deck of crossref-deleted subgraphs: Let the crossref-deleted subgraph with respect to $v$ be the $v$-rooted graph constructed from $G$ by deleting all edges between vertices that have the same distance from $v$.

Note that the vertex-deleted subgraph with respect to $v$ is nothing but the $v$-rooted graph constructed from $G$ by deleting all edges between $v$ and its neighbours.

I am not good in systematically constructing counterexamples, and I do not have very much intuition about general graphs. So, any counterexample to one of the candidates above would be very welcome.

What I do know is that a) trees are trivially reconstructible from their deck of crossref-deleted subgraphs, that b) graphs with one node of which the distinguishing neighbourhood is the whole graph are trivially reconstructible from their deck of distinguishing neighbourhoods, and that c) reconstructing (very) small graphs from one of the decks above is fun.

share|improve this question
    
What is the distinguishing neighborhood of a vertex in a symmetric graph? –  JBL May 19 '10 at 13:43
    
It's the same for all conjugate vertices. If the graph is vertex-transitive, it should be the 1-neighbourhood. –  Hans Stricker May 19 '10 at 13:57

1 Answer 1

up vote 7 down vote accepted

I suspect that there are counterexamples to all three of your proposals. For example, you clarified that the distinguishing neighborhood of a vertex-transitive graph is just its 1-neighborhood. Then the dodecahedral graph and the Desargues graph will have the same decks; in each case you'll just have twenty copies of $K_{1,3}$. Similarly, although I don't have an explicit counterexample offhand, I suspect that if you examine strongly regular graphs with the same degree and number of vertices, you will find plenty of pairs of graphs with the same decks of sub-maximal neighborhoods. (Strongly regular graphs have diameter 2 so again you're just looking at 1-neighborhoods.)

As for your question of what other reconstruction conjectures there are, the most famous is the edge reconstruction conjecture. There is also the vertex-switching reconstruction conjecture and the $k$-reconstruction conjecture (see Bondy's Graph Reconstructor's Manual for definitions). For more examples, you could try contacting Mark Ellingham at Vanderbilt, who keeps a list of papers on the reconstruction conjecture.

share|improve this answer
    
Thanks for your valuable hints! But it might still be the case, that almost all graphs could be reconstructed by one of the decks. What do you think? –  Hans Stricker May 19 '10 at 20:17
    
Bollobas famously proved a conjecture of Harary and Plantholt that almost every graph can be reconstructed from just three cards from the usual deck (<i>J. Graph Theory</i> 14 (1990), 1-4). In other words, once you relax "all" to "almost all" then reconstruction becomes "easy." So it's plausible that your decks will suffice for almost all graphs, but such a theorem would not be particularly interesting. –  Timothy Chow May 20 '10 at 2:02
    
I didn't understand the 3-card-theorem this way (that reconstruction has become "easy") but that way: that the vertex-deleted subgraphs are often enough very similar to the original graph and differ only locally. (That's why I don't find vertex-deleted subgraphs very compelling.) I would not expect that an analogue of the 3-card-theorem holds for one of my decks, which I "like" better, because their cards generally don't resemble the original graph too much. By the way: Why would "such a theorem" not be interesting? Bollobas' seems to be interesting, at least it's famous. –  Hans Stricker May 20 '10 at 6:50
3  
I think the reason the original reconstruction conjecture is interesting is that we seem to have so much information about the graph, yet nobody can see how to reconstruct the graph from it. Bollobas's result is interesting because it shows that our intuition that the standard deck is overkill is correct for random graphs (but I would not find Bollobas's result so interesting if we didn't already know that the reconstruction conjecture is hard). Your decks are complicated and I need to be convinced why they're interesting, as opposed to any number of other complicated decks one could define. –  Timothy Chow May 23 '10 at 21:51
2  
A non-constructive proof would be surprising, but certainly conceivable. Note, though, that you have to be a little careful with what you mean by "non-constructive." If the reconstruction conjecture is true then there is always an algorithm to reconstruct the graph: Simply exhaust over all possibilities until you find the right graph. "Non-constructive" would have to mean that the proof would not provide a <i>good</i> algorithm (say, a polynomial-time algorithm) for reconstructing the graph. –  Timothy Chow May 28 '10 at 4:48

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.