The polynomial reconstruction problem: The first 50 years

Abstract

The problem of reconstructing the characteristic polynomial of a graph of order at least 3 from the collection of characteristic polynomials of its vertex-deleted subgraphs was posed by Cvetković in 1973 as a spectral counter part to the well-known Ulam's reconstruction conjecture. Over the last 50 years, this problem has received notable attention, many positive results have been obtained, but in the general case the problem is still unresolved. In particular, no counter example is found in literature. In this expository paper we survey classical and some more recent results concerning the polynomial reconstruction problem, discuss some related problems, variations and generalizations.