Recovering the characteristic polynomial of a graph from entries of the adjugate matrix

Abstract

The adjugate matrix of G, denoted by adj(G), is the adjugate of the matrix xI − A, where A is the adjacency matrix of G. The polynomial reconstruction problem (PRP) asks if the characteristic polynomial of a graph G can always be recovered from the multiset PD(G) containing the n characteristic polynomials of the vertex-deleted subgraphs of G. Noting that the n diagonal entries of adj(G) are precisely the elements of PD(G), we investigate variants of the PRP in which multisets containing entries from adj(G) successfully reconstruct the characteristic polynomial of G. Furthermore, we interpret the entries off the diagonal of adj(G) in terms of characteristic polynomials of graphs, allowing us to solve versions of the PRP that utilize alternative multisets to PD(G) containing polynomials related to characteristic polynomials of graphs, rather than entries from adj(G).