A Proof of Brouwer's Toughness Conjecture

DOI10.1137/20M1372652zbMath1465.05102arXiv2010.05065OpenAlexW3161585086WikidataQ123249608 ScholiaQ123249608MaRDI QIDQ4990394

Xiaofeng Gu

Publication date: 28 May 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2010.05065

zbMATH Keywords

eigenvaluetoughnessexpander mixing lemmapseudorandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Connectivity (05C40)

Related Items (8)

Toughness and normalized Laplacian eigenvalues of graphs ⋮ ℓ $\ell $‐Connectivity and ℓ $\ell $‐edge‐connectivity of random graphs ⋮ Spectral bounds for the vulnerability parameters of graphs ⋮ Binding number, \(k\)-factor and spectral radius of graphs ⋮ Spectral conditions for connectivity, toughness and perfect \(k\)-matchings of regular graphs ⋮ Graph toughness from Laplacian eigenvalues ⋮ Toughness, Hamiltonicity and spectral radius in graphs ⋮ \(\ell\)-connectivity, integrity, tenacity, toughness and eigenvalues of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The spectrum and toughness of regular graphs
• Explicit construction of linear sized tolerant networks
• Eigenvalues and perfect matchings
• Tough Ramsey graphs without short cycles
• Toughness and spectrum of a graph
• Toughness and triangle-free graphs
• Toughness in pseudo-random graphs
• Tough graphs and Hamiltonian circuits.
• Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs

This page was built for publication: A Proof of Brouwer's Toughness Conjecture