Constraint failure boundary G; The Exact Boundary of Spectral Determination of Isomorphism in the Family of Single-Bridge Trees
The exact boundary of spectral determination of isomorphism within the familyof single-bridge trees can be stated completely: the boundary is the size group. Thestandard building block is the four-arm signature (a,b,c,d), subject to a+b = m−1and c +d = n−1, taken modulo the interchange of the two blocks and the mirrorings of each block; the bidirectionally computable correspondence between thespectral object and the signature is given by a deletion–contraction closed form ofthe matching polynomial. This paper proves conclusions on four layers. The firstlayer is the structure theorem (L4, unconditional closure within the family): forarbitrary m,n ≥ 2, within a fixed size group the two maps between characteristic polynomials and signature orbits are mutually inverse, and isomorphism holdsif and only if the spectra coincide; the proof is closed by two purely combinatorial lemmas—the arm multiset can be recovered from Q by peeling, and the sidepartition is unique—with no missing step. The second layer is the core lemma(L3): a complete proof of the deletion–contraction closed form, together with anexecutable peeling algorithm that recovers the signature from the characteristicpolynomial, whose correctness is a direct corollary of the structure theorem. Thethird layer consists of concrete corollaries (L2): explicit closed forms for the matching numbers m1, m2, m3 in terms of the four arms, a lower bound for the spectralradius, a closed-form treatment of the degenerate boundary (an arm of length 0),and a small-vertex cospectral pair showing that in the general family of trees thematching-number vector does not suffice to determine a tree. The fourth layeris the sharpness of the boundary: across size groups there exist non-isomorphiccospectral pairs, the minimal witness having 10 vertices, namely T(3,7,1,2) andT(5,5,1,1)—existence is given by a finite verification in this paper, and minimalityis closed unconditionally by Proposition 9.1 via the exact exclusion of eight pairs ofsize groups; hence fixing the size group is an essential hypothesis of the structuretheorem, not a technical restriction. All numerical readings are produced by external scripts in pure integer polynomial arithmetic and are disclosed in advance in aseparate chapter; this paper does not promote machine-check readings to theorems,and the division of labor between machine checks and proofs is marked at everyoccurrence in the main text.
Authors
- changzheng zhou (ORCID: https://orcid.org/0009-0002-4186-7877)
- ziqing zhou (ORCID: https://orcid.org/0009-0005-6883-6300)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-16
- DOI
- https://doi.org/10.5281/zenodo.24272311
- Primary Topic
- Graph theory and applications
- Type
- preprint