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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Constraint failure boundary G; The Exact Boundary of Spectral Determination of Isomorphism in the Family of Single-Bridge Trees

changzheng zhou, ziqing zhou
2 links
Zenodo (CERN European Organization for Nuclear Research)
Graph theory and applications
preprint

Constraint failure boundary G; The Exact Boundary of Spectral Determination of Isomorphism in the Family of Single-Bridge Trees

changzheng zhou, ziqing zhou
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Graph theory and applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon