2025/03/22 by Spier, Thomás Jung
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2503.17853
The polynomial reconstruction problem, introduced by Cvetković in 1973, asks whether the characteristic polynomial ϕG of a graph G with at least 3 vertices can be reconstructed from the polynomial deck \ϕG ∖ i\i ∈ V(G). In this work, we prove that ϕG \pmod4 can be reconstructed from the polynomial deck if the number of vertices in G is even or if the rank of the walk matrix of G over \mathbbF2 is less than \lceil n/2 \rceil. We also prove that for every graph G, ϕ^G\pmod4 can be computed from ϕG\pmod4, strengthening a recent result by Ji, Tang, Wang and Zhang. Finally, Hagos showed that the pair of characteristic polynomials (ϕG, ϕ^G) is reconstructible from the generalized polynomial deck \(ϕG ∖ i, ϕ^G ∖ i)\i ∈ V(G). We also present an efficient version of this result that requires less information.