05C50 Online Seminar: Alexander Farrugia

The adjugate matrix of a graph G on n vertices, denoted by adj G, is the adjugate of xI - A, where A is the 0-1 adjacency matrix of the graph. The entries of this matrix are polynomials in the variable x, of varying degrees. We shall first outline introductory results on the adjugate matrix, in the process noting that the diagonal entries of adj G are the characteristic polynomials of the n vertex-deleted subgraphs of G.

The Polynomial Reconstruction Problem asks if it is possible to deduce the characteristic polynomial of G from those of its vertex-deleted subgraphs. Last year, it was its 50th year anniversary since it was put forward for the first time by Cvetković in 1973, yet it has resisted proof (or the discovery of a counterexample) during all this time. In view of the previous paragraph, the problem may be restated as attempting to find the characteristic polynomial of G from the diagonal entries of adj G. We then extend this idea to successfully deduce the characteristic polynomial of G from various subsets of the entries of adj G, some of which include its diagonal entries, and others that don’t.

PREPRINT