Efficient reconstruction of the characteristic polynomial
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909549391249408 |
|---|---|
| author | Spier, Thomás Jung |
| author_facet | Spier, Thomás Jung |
| contents | 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 \setminus i}\}_{i \in V(G)}$. In this work, we prove that $ϕ^G \pmod{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$, $ϕ^{\overline{G}}\pmod{4}$ can be computed from $ϕ^G\pmod{4}$, strengthening a recent result by Ji, Tang, Wang and Zhang. Finally, Hagos showed that the pair of characteristic polynomials $(ϕ^G, ϕ^{\overline{G}})$ is reconstructible from the generalized polynomial deck $\{(ϕ^{G \setminus i}, ϕ^{\overline{G} \setminus i})\}_{i \in V(G)}$. We also present an efficient version of this result that requires less information. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_17853 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient reconstruction of the characteristic polynomial Spier, Thomás Jung Combinatorics 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 \setminus i}\}_{i \in V(G)}$. In this work, we prove that $ϕ^G \pmod{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$, $ϕ^{\overline{G}}\pmod{4}$ can be computed from $ϕ^G\pmod{4}$, strengthening a recent result by Ji, Tang, Wang and Zhang. Finally, Hagos showed that the pair of characteristic polynomials $(ϕ^G, ϕ^{\overline{G}})$ is reconstructible from the generalized polynomial deck $\{(ϕ^{G \setminus i}, ϕ^{\overline{G} \setminus i})\}_{i \in V(G)}$. We also present an efficient version of this result that requires less information. |
| title | Efficient reconstruction of the characteristic polynomial |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.17853 |