A lower bound of toughness of regular graphs: in terms of second largest eigenvalue
Wenqian Zhang · 2026
Read A lower bound of toughness of regular graphs: in terms of second largest eigenvalue by Wenqian Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-00627.txt.
Description
Wenqian Zhang proves a spectral lower bound on the toughness of regular graphs. Toughness measures how hard a network is to shatter: remove a set of vertices, count the pieces left behind, and toughness is the worst-case ratio of removed vertices to pieces. It captures, in one number, a network's resistance to fragmentation. Zhang's setting is a connected regular graph where every vertex has the same degree, at least three, excluding the complete graph.
The bound is expressed through the graph's second-largest eigenvalue, a quantity that measures how well the graph expands and mixes. Roughly, the theorem says toughness is at least a specific combination of the degree and that eigenvalue, capped at one. When the eigenvalue is small relative to the degree, the graph is guaranteed hard to break apart. Such results are valued because eigenvalues are computable, while toughness itself is notoriously hard to calculate directly.
Catalog record
| CREATOR | Wenqian Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 16 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.00627