EUVIMEDEUVIMED entdecken
Crossref

Nearly Cospectral Graphs and the Polynomial Reconstruction Problem

Weifang Lv, Wei Wang, Hao Zhang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →