Metraipolis › archive › dc_8878bf0cddee
A Sharp Matching-Number Threshold for Spectral-Walk Determination of Trees — arXiv:2608.21851
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.21851
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-18T08:29:54.060Z
- SHA-256 of the archived text
eae6f5b497ac3f65ea777756bd8d6bde8b5f513a634ed9ef17001ed1440f5533- Stable URL of this page
https://metraipolis.com/documento/dc_8878bf0cddee
How to cite
A Sharp Matching-Number Threshold for Spectral-Walk Determination of Trees — arXiv:2608.21851 — arXiv (en), https://arxiv.org/abs/2608.21851 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8878bf0cddee (Metraipolis archive dc_8878bf0cddee, sha256 eae6f5b497ac3f65ea777756bd8d6bde8b5f513a634ed9ef17001ed1440f5533)
BibTeX
@misc{dc8878bf0cddee,
title = {A Sharp Matching-Number Threshold for Spectral-Walk Determination of Trees — arXiv:2608.21851},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.21851},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8878bf0cddee; sha256 eae6f5b497ac3f65ea777756bd8d6bde8b5f513a634ed9ef17001ed1440f5533},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.21851. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The spectral characterization of graphs is a central problem in spectral graph theory. In this paper we study when a tree is determined, among trees, by its generalized spectrum. We use the equivalent formulation given by the adjacency spectrum together with the total-walk sequence $W_k(G)=\mathbf 1^{\mathsf T}A(G)^k\mathbf 1$. We determine the exact matching-number threshold for this tree-level reconstruction problem. If $T$ and $T'$ are trees with matching number at most 4 and have the same adjacency spectrum and the same total-walk sequence, then $T\cong T'$. Moreover, in this range it is enough to require equality of $W_k$ for $3\le k\le8$. The bound is sharp: for every positive integer $m$ we construct a pair of non-isomorphic trees with matching number 5 having the same adjacency spectrum and identical total-walk sequences. The proof of the positive result is based on a finite-core reduction and an algebraic reconstruction of the possible pendant attachments.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-25 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.21851 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T08:27:54.391Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).