Nearly Cospectral Graphs and the Polynomial Reconstruction Problem

Abstract

The polynomial reconstruction problem, proposed by Cvetković in 1973, asks whether the characteristic polynomial $\phi(G;x)$ of a graph $G$ with at least 3 vertices can be reconstructed from the polynomial deck $\mathcal{P}(G)=\{\phi(G-v_i;x)\}_{v_i\in V(G)}$. In 2000, Hagos proposed a question of whether $\phi(G;x)$ is reconstructible from the two decks $\mathcal{P}(G)$ and $\mathcal{P}(\bar{G})$. Recently, strengthening a theorem of Ji et al. (2024), Spier (2025) proved that the characteristic polynomials of two graphs are congruent modulo 4 if and only if the characteristic polynomials of their complements are congruent modulo 4. Motivated by the above, we prove that for any two graphs $G$ and $H$, if $\phi(G;x)-\phi(H;x)\equiv c\pmod{4}$ and $\phi(\bar{G};x)-\phi(\bar{H};x)\equiv d\pmod{4}$ for two constants $c$ and $d$, respectively, then $c\equiv d\pmod{4}$. In particular, if $n$ is even, then $c\equiv d\equiv 0\pmod{4}$. This strengthens Spier's results, and provides some non-trivial information about the constant coefficients of $\phi(G;x)$ and $\phi(H;x)$ for any potential counterexample pair $(G,H)$ to the polynomial reconstruction problem. We also obtain a similar result for any potential counterexample pair $(G,H)$ to the problem proposed by Hagos in 2000.