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

CREATORWenqian Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE16 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.00627

Browse the full library · About the Tower of Babel