The spectrum and toughness of regular graphs

DOI10.1016/j.dam.2013.12.004zbMath1298.05200arXiv1312.2247MaRDI QIDQ403562

Wiseley Wong, Sebastian M. Cioabă

Publication date: 29 August 2014

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

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

zbMATH Keywords

strongly regular graph; independence number; toughness; eigenvalues of graphs; Hoffman ratio bound

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05E30: Association schemes, strongly regular graphs

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

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spectra of graphs
• Matchings in regular graphs from eigenvalues
• The connectivity of strongly regular graphs
• The complexity of recognizing tough cubic graphs
• 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
• Closed walks and eigenvalues of abelian Cayley graphs
• Tough graphs and Hamiltonian circuits.
• Algebraic conditions for t-tough graphs
• Hamiltonian results inK1,3-free graphs