The toughness of Kneser graphs

DOI10.1016/j.disc.2021.112484zbMath1467.05142arXiv2008.08183MaRDI QIDQ2037560

Tanay Wakhare, Sebastian M. Cioabă, Davin Park, Nathan Hayes, Anthony Ostuni, Wiseley Wong, Amartya S. Banerjee

Publication date: 8 July 2021

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

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

zbMATH Keywords

graph connectivity; toughness; Kneser graph

Mathematics Subject Classification ID

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C40: Connectivity

05C45: Eulerian and Hamiltonian graphs

Cites Work

• The spectrum and toughness of regular graphs
• Kneser's conjecture, chromatic number, and homotopy
• On \(k\)-chromatically connected graphs
• A short proof of Kneser's conjecture
• Triangle-free Hamiltonian Kneser graphs
• A combinatorical proof of Kneser's conjecture
• Tough Ramsey graphs without short cycles
• Toughness and spectrum of a graph
• Interlacing eigenvalues and graphs
• Not every 2-tough graph is Hamiltonian
• Toughness in graphs -- a survey
• Tough graphs and Hamiltonian circuits.
• The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton–Milner family
• Vertex-transitive graphs that remain connected after failure of a vertex and its neighbors
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Erdős–Ko–Rado Theorems: Algebraic Approaches
• A New Short Proof of Kneser's Conjecture
• A spectral approach to bandwidth and separator problems in graphs
• Sparse Kneser graphs are Hamiltonian
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Connectivity of transitive graphs
• Bipartite Kneser graphs are Hamiltonian
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item