Nearly Cospectral Graphs and the Polynomial Reconstruction Problem
The Electronic Journal of Combinatorics · 24.04.2026 · 33 (2)
DOI: 10.37236/14650 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 24.04.2026. Verfasst von Weifang Lv und 2 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
Lv, W., Wang, W., & Zhang, H. (2026). Nearly Cospectral Graphs and the Polynomial Reconstruction Problem. The Electronic Journal of Combinatorics, 33(2). https://doi.org/10.37236/14650
Vancouver
Lv W, Wang W, Zhang H. Nearly Cospectral Graphs and the Polynomial Reconstruction Problem. The Electronic Journal of Combinatorics. 2026;33(2). doi:10.37236/14650
BibTeX
@article{Lv2026,
author = {Lv, Weifang and Wang, Wei and Zhang, Hao},
title = {Nearly Cospectral Graphs and the Polynomial Reconstruction Problem},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {2},
doi = {10.37236/14650}
}
EUVIMED