Delphi.science

Graphs attaining Haemers' toughness bound

Source: arxiv.org/abs/2611.18193

Yifan Li, Cheng Yeaw Ku

arXivarxiv/2611.18193Nov 13, 2026math.COscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'