9 - Reconstructing from Subdecks

Summary

Although graph theorists are still very far away from solving the Reconstruction Problem, in most cases where a class of graphs has been shown to be reconstructible it has turned out that only a few of the graphs in the deck were needed. So it seems that, in many cases at least, there might actually be more than sufficient information in D(G) to determine G uniquely. This has prompted many researchers to study variants of the Reconstruction Problem in which only some of the information in D(G) is given. Of course, these problems are more difficult than the original form of the Reconstruction Problem, so there is little hope of solving them in general. But their study has given rise to interesting problems, some of which use theory developed in earlier chapters. We shall consider in the next three sections three such variants of the Reconstruction Problem.

The endvertex-deck

One of the first classes of graphs that was shown to be reconstructible was trees [120]. This early result was subsequently improved so that it was shown that, for any tree T, the endvertex-deck D₁(T) consisting of those subgraphs T − v with v an endvertex is sufficient to reconstruct T. One natural question that arises is therefore whether, given a graph G with a sufficiently large number of endvertices, G is endvertex-reconstructible, that is, reconstructible from its endvertex-deck D₁(G). Bryant has shown that this is, in fact, not true. His result is a clever use of Bouwer's Theorem and it requires the following lemma, whose easy proof is left as an exercise.

Lemma 9.1Let F = ℤ₂be the binary field and let X be the k-dimensional vector space consisting of all k-tuples of elements of F. Let Γ be the group of

permutations that are linear transformations on X. Let A be a basis of X and let B be a set of k vectors of X whose sum is zero but such that any proper subset of B is linearly independent. Then,

Theorem 9.2 (Bryant)For any positive integer k there exists a graph G with k endvertices such that G is not endvertex-reconstructible.