Graphs attaining Haemers' toughness bound
Source: arxiv.org/abs/2611.18193
Haemers \cite{Haemers2020} conjectured that every connected noncomplete graph $G$ satisfies $t(G)\geqslantμ_2/(μ_n-δ)$, where $t(G)$ is the toughness of $G$, $μ_2$ and $μ_n$ are its algebraic connectivity and Laplacian spectral radius, and $δ$ is its minimum degree. Greaves and Zhu \cite{GreavesZhu2026} recently proved this conjecture, leaving the equality case open. We characterize all graphs attaining equality: a graph attains equality if and only if its complement has a complete component whose order is at least the Laplacian spectral radius of every other component. Equivalently, its…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.18193
curl -X POST /api/v1/records/arxiv/2611.18193/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.18193/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'