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

A Proof of Brouwer's Toughness Conjecture, The toughness of Kneser graphs, Toughness and normalized Laplacian eigenvalues of graphs, Toughness in pseudo-random graphs, Spanning trees of bounded degree, connectivity, toughness, and the spectrum of a graph, Sharp spectral bounds for the vertex-connectivity of regular 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, 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