10
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ What is the distinguishing neighborhood of a vertex in a symmetric graph? $\endgroup$
    – JBL
    Commented May 19, 2010 at 13:43
  • $\begingroup$ It's the same for all conjugate vertices. If the graph is vertex-transitive, it should be the 1-neighbourhood. $\endgroup$
    – Hans-Peter Stricker
    Commented May 19, 2010 at 13:57

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Hans-Peter Stricker
    Commented May 19, 2010 at 20:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – Timothy Chow
    Commented May 20, 2010 at 2:02
  • 3
    $\begingroup$ 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. $\endgroup$
    – Timothy Chow
    Commented May 23, 2010 at 21:51
  • 1
    $\begingroup$ By the way: I contacted Mark Ellingham, and he pointed me to this paper: C. D. Godsil, I. Krasikov and Y. Roditty, Reconstructing graphs from their $k$-edge deleted subgraphs, J. Combin. Theory Ser. B 43 no. 3 (1987) 360-363. MR 89a:05106. Maybe this makes the answer to my question complete. $\endgroup$
    – Hans-Peter Stricker
    Commented May 26, 2010 at 21:17
  • 3
    $\begingroup$ 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. $\endgroup$
    – Timothy Chow
    Commented May 28, 2010 at 4:48

You must log in to answer this question.

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