Efficient reconstruction of the characteristic polynomial

Abstract

The polynomial reconstruction problem, introduced by Cvetković in 1973, asks whether the characteristic polynomial $\ddot{I}{•}^G$ of a graph $G$ with at least $3$ vertices can be reconstructed from the polynomial deck $\{\ddot{I}{•}^{G\setminus i}{\}}_{i\in V(G)}$. In this work, we prove that $\ddot{I}{•}^G(\mathrm{mod}4)$ 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 ${\mathbb{F}}_2$ is less than $\lceil n/2\rceil$. We also prove that for every graph $G$, $\ddot{I}{•}^{\overline{G}}(\mathrm{mod}4)$ can be computed from $\ddot{I}{•}^G(\mathrm{mod}4)$, strengthening a recent result by Ji, Tang, Wang and Zhang. Finally, Hagos showed that the pair of characteristic polynomials $(\ddot{I}{•}^G,\ddot{I}{•}^{\overline{G}})$ is reconstructible from the generalized polynomial deck $\{(\ddot{I}{•}^{G\setminus i},\ddot{I}{•}^{\overline{G}\setminus i}){\}}_{i\in V(G)}$. We also present an efficient version of this result that requires less information.

26 pages