We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
Published online by Cambridge University Press: 05 June 2016
The Reconstruction Problem is considered one of the foremost unsolved problems in graph theory. In this chapter we shall define the two principal variants of this problem, and we shall give some of the most basic results related to these two problems. We shall also try to convey the flavour of what it takes to reconstruct a class of graphs and how this is related to important graph theoretic properties of the class.
A look at some of the surveys on the Reconstruction Problem, for example, [31, 32, 140, 203], will show that a considerable number of papers on this topic have been published. Also, many reconstruction proofs involve ad hoc case-by-case analysis; at this stage of our knowledge of the problem, it seems impossible to simplify these proofs significantly. It is therefore not the aim of the remaining chapters of this book to give anything like an exhaustive treatment of these results. The reader can see a more complete coverage of the Reconstruction Problem by consulting surveys such as the ones cited earlier and then going to the papers themselves where the results were obtained.
What we shall do in this chapter is give those basic definitions, techniques and results which can be presented succinctly and which are often used in most work on the reconstruction of graphs. We shall also discuss in some detail the reconstruction of particular classes of graphs. In the next chapter we shall look at variations of the main Reconstruction Problem that have been formulated, and in the final two chapters we shall present two general techniques that have been developed and that allow a systematic treatment of reconstruction rather than an ad hoc one for particular graph classes. In these four chapters we shall also try to emphasise as much as possible those aspects of the reconstruction of graphs that are related to symmetry properties of graphs, and we shall as much as possible try to present results that use ideas and theorems that we have already presented in earlier chapters.
Definitions
Given a graph G, the collection of its vertex-deleted subgraphs G − v for all v ∈ V(G) is called the deck of G and is denoted by D(G).
To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.
