The polynomial reconstruction problem, proposed by Cvetkovic more than fifty years ago, asks whether the characteristic polynomial  of a graph  with at least 3 vertices can be reconstructed from the polynomial deck . In 2000, Hagos proposed a question of whether  is reconstructible from the two decks  and . 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  and , if and for two constants c and d, respectively, then . In particular, if  is even, then  This strengthens Spier’s results, and provides some non-trivial information about the constant coefficients of  and  for any potential counterexample pair  to the polynomial reconstruction problem. We also obtain a similar result for any potential counterexample pair  to the problem proposed by Hagos in 2000.

王卫，西安交通大学数学与统计学院教授、博士生导师。主要研究领域为代数图论与组合最优化。在图谱理论的研究中对图的广义谱刻画问题做出了一些原创性的工作，在组合优化领域中对一些NP-困难组合优化问题设计出了一些好的近似算法。在J. Combin. Theory,Ser B, European J. Combin. 以及IEEE/ACMTransactions系列等组合图论刊物上发表研究论文100余篇，主持（完成）国家自然科学基金面上项目多项。目前担任中国运筹学会图论与组合分会常务理事、陕西省工业与应用数学学会理事长及国际刊物“Linear Algebra Appl.” “Discrete Mathematics, Algorithms and Applications”编委等。