On graph reconstruction and polynomial reconstruction

Abstract

The Reconstruction Conjecture (RC) asks whether all unlabelled, finite, simple graphs of order at least three are uniquely reconstructible from the deck of vertex-deleted subgraphs. This was first considered in 1941 by Kelly and Ulam when P. J. Kelly wrote his dissertation under S. M. Ulam. The RC is one of the most engaging open problems in graph theory. This is evidenced by the vast amount of literature generated in addressing this problem and also in the different approaches taken in tackling the conjecture. This conjecture is deceptively simple, as a simple finite graph can always be found to be a reconstruction of its deck however the main difficulty is in proving the uniqueness of the graph. The RC has given rise to many variant problems, one such variation is the Polynomial Reconstruction Problem (PRP). The PRP claims that the characteristic polynomial of a graph is uniquely determined from its polynomial deck, where the polynomial deck consists of the characteristic polynomials of the vertex-deleted subgraphs of the graph. This problem was originally proposed by Gutman and Cvetkovic in 1975 and this initially appears to be a simpler problem than the RC since the polynomial deck of a graph determines the characteristic polynomial up to the constant term. However in general there is no direct way of determining the constant term from the polynomial deck and hence it is also open in general. Although it is not yet resolved whether the deck of a graph uniquely determines the graph and similarly whether the polynomial deck uniquely determines the characteristic polynomial, both these decks do ascertain many graph and spectral properties. In this dissertation we state that the properties that are reconstructible from the deck of a graph are the degrees of all the vertices, the number of subgraphs isomorphic to any graph of order less than that of the graph and also the characteristic polynomial of the graph. When considering the PRP, we outline that the degrees of all the vertices, the length of the shortest odd cycle, the number of quadrangles and the number of pentagons are all polynomial reconstructible from the polynomial deck.