Search

Let G be a simple graph and { 1 , 2 , ... , n } be its vertex set. The polynomial reconstruction problem asks the question: given a deck P (G) containing the n characteristic polynomials of the vertex deleted subgraphs G − 1 , G − 2 , ..., G − n of G, can ϕ (G , x) , the characteristic polynomial of G, be reconstructed uniquely? To date, this long-standing problem has only been solved in the affirmative for some specific classes of graphs. We prove that if there exists a vertex v such that more than half of the eigenvalues of G are shared with those of G − v , then this fact is recognizable from P (G) , which allows the reconstruction of ϕ (G , x) . To accomplish this, we make use of determinants of certain walk matrices of G. Our main result is used, in particular, to prove that the reconstruction of the characteristic polynomial from P (G) is possible for a large subclass of disconnected graphs, strengthening a result by Sciriha and Formosa. [ABSTRACT FROM AUTHOR]