[Math] Reconstruction conjecture: Can other decks do the job

graph theorygraph-reconstruction

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.

Best Answer

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.

Related Question