Polynomial reconstruction : old and new techniques

Abstract

The Polynomial Reconstruction Problem (PRP) asks whether for a graph G of order at least three, the characteristic polynomial can be reconstructed from the p-deck PD(G) of characteristic polynomials of the one-vertex-deleted subgraphs. The problem is still open in general but has been proved for certain classes of graphs. We discuss the tools and techniques most commonly used and survey the main positive results obtained so far, pointing out the classes of graphs for which we know that the PRP has a positive resolution.