On Polynomial Reconstruction of Disconnected Graphs

Abstract

Let H be a disconnected graph with connected components H₁, H₂, ..., Ht. If the characteristic polynomial of H were not reconstructible from the deck of characteristic polynomials of its one-vertex deleted subgraphs, then H would consist of exactly two connected components of the same order. We show that if H has a pendant edge in the component with the larger number of edges or if the smaller component of H is a tree, then H is polynomial reconstructible.