“A Graph Reconstructor's Manual”

Summary

THE RECONSTRUCTION CONJECTURE

Fifty years have elapsed since the Reconstruction Conjecture was proposed, by S.M. Ulam and P.J. Kelly, in 1941. This seems a fitting time, therefore, to report on its status. Because particular aspects of this elusive question have been amply addressed in a recent flurry of expository articles (Ellingham, 1988; Lauri, 1987; Manvel, 1988; Stockmeyer, 1988), we have chosen to present here an overview of the techniques employed, a manual to reconstruction. Each technique will be illustrated and its applications noted, accompanied by appropriate references. For clarity and simplicity, we shall concentrate on the two principal open questions of reconstruction, namely the Reconstruction Conjecture itself and its companion version for edges, the Edge Reconstruction Conjecture, formulated by F. Harary in 1964. Some related questions, amenable to the same or similar techniques, will be discussed briefly at the end of the article. We start with the basic definitions.

1.1 Definitions. A vertex-deleted subgraph of a graph G is a subgraph G – v obtained by deleting a vertex v and its incident edges. The deck of a graph G is the family of (unlabelled) vertex-deleted subgraphs of G; these are the cards of the deck. A reconstruction of a graph G is a graph H with the same deck as G. A graph G is reconstructible if every reconstruction of G is isomorphic to G. Similar definitions apply to digraphs and hypergraphs.