Graph reconstruction - some techniques and new problems

Abstract

This paper is mostly of an expository nature. Without in any way attempting to provide a comprehensive survey of the work done on the Reconstruction Problem, we shall l ook at a few results obtained in recent years, and we s hall try to identify some common reconstruction techniques which have been developed independently by different investigators and which could therefore help to unify some aspects of their work . A look at these results will also permit us to discuss some open questions which they bring up. In the final section of the paper, we shall look at the notion of reconstruction numbers which has recently been introduced by Harary and Plantholt. Basically, a reconstruction number is the minimum number of vertex-deleted, or edge-deleted, subgraphs required to determi ne a graph uniquely. We shall discuss the main results obtained so far, particularly for maximal planar graphs and trees, and we shall also consider some open problems.