On the reconstruction of the characteristic polynomial of a graph (Q1970575)

\(P_{G}(\lambda) = \text{det}(\lambda I - A) = {\lambda }^n + a_{1}{\lambda }^{n-1}+ \cdots +a_{n-1}\lambda +a_{n} \) is the characteristic polynomoial of the graph \(G\) with adjacency matrix \(A\). Let \({\mathcal P}(G)\) be the collection of characteristic polynomials \(P_{G-x_{i}}(\lambda)\) of the vertex deleted subgraphs \(G-x_{i}\) \((i=1,2,\ldots ,n)\) of \(G\). The author reconsiders the problem of reconstructing \(P_{G}(\lambda)\) uniquely from \({\mathcal P}(G)\), posed by him in 1973. It is well known that this can be solved if \(a_{n}\) can be found from \({\mathcal P}(G)\) and that this is possible if an eigenvalue of \(G\) is known. The problem has been solved earlier for some classes of graphs like regular graphs, a broad class of bipartite graphs, etc. The degree sequence is known to be reconstructible from the deck \({\mathcal P}(G)\). In this paper the author proves that the length of the shortest odd circuit and the number of such circuits and the number of triangles, quadrangles and pentagons, the number of closed walks of length \(k\) \((=0,1,\ldots ,n-1)\) starting and terminating at a vertex \(x_{i}\) and the spectral moments can be computed from \({\mathcal P}(G)\). He also considers a couterexample pair of graphs \(G\) and \(H\) with \({\mathcal P}(G) = {\mathcal P}(H)\) but with different values for \(a_{n}\) and in the case where \(G\) is a tree with a 1-factor, derives several properties of the graph \(H\) (like \(H\) is disconnected, etc.). The problem however, still remains unresolved.