Let G be a simple graph and $\{1,2,\dots ,n\}$ be its vertex set. The polynomial reconstruction problem asks the question: given a deck $\mathcal{P}\left(G\right)$ containing the n characteristic polynomials of the vertex deleted subgraphs $G-1$, $G-2$, …, $G-n$ of G, can $\varphi (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 $\mathcal{P}\left(G\right)$, which allows the reconstruction of $\varphi (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 $\mathcal{P}\left(G\right)$ is possible for a large subclass of disconnected graphs, strengthening a result by Sciriha and Formosa.

A graph is said to be non-singular if it has no eigenvalue equal to zero; otherwise it is singular. Molecular graphs that are non-singular and also have the property that all subgraphs of them obtained by deleting a single vertex are themselves singular, known as NSSD graphs, are of importance in the theory of molecular π-electron conductors; NSSD = non-singular graph with a singular deck. Whereas all non-singular bipartite graphs (therefore, the molecular graphs of all closed-shell alternant conjugated hydrocarbons) are NSSD, the non-bipartite case is much more complicated. Only a limited number of non-bipartite molecular graphs have the NSSD property. Several methods for constructing such molecular graphs are presented. This work is licensed under a Creative Commons Attribution 4.0 International License