The spectrum and toughness of regular graphs

DOI10.1016/J.DAM.2013.12.004MaRDI QIDQ403562zbMATH OpenOpenAlexFDO

Authors Sebastian Cioaba, Wiseley Wong

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 grapheigenvalues of graphsindependence numbertoughnessHoffman ratio bound

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Association schemes, strongly regular graphs (05E30)

Abstract: In 1995, Brouwer proved that the toughness of a connected $k$-regular graph $G$ is at least $k/lambda-2$, where $lambda$ is the maximum absolute value of the non-trivial eigenvalues of $G$. Brouwer conjectured that one can improve this lower bound to $k/lambda-1$ and that many graphs (especially graphs attaining equality in the Hoffman ratio bound for the independence number) have toughness equal to $k/lambda$. In this paper, we improve Brouwer's spectral bound when the toughness is small and we determine the exact value of the toughness for many strongly regular graphs attaining equality in the Hoffman ratio bound such as Lattice graphs, Triangular graphs, complements of Triangular graphs and complements of point-graphs of generalized quadrangles. For all these graphs with the exception of the Petersen graph, we confirm Brouwer's intuition by showing that the toughness equals $k/(-lambd{a}_{min})$, where $lambd{a}_{min}$ is the smallest eigenvalue of the adjacency matrix of the graph.

Recommendations

• A proof of Brouwer's toughness conjecture
• Toughness and spectrum of a graph
• Toughness and normalized Laplacian eigenvalues of graphs
• The toughness of Kneser graphs
• Toughness in pseudo-random graphs

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 997668 (Why is no real title available?)
• scientific article; zbMATH DE number 1472146 (Why is no real title available?)
• Algebraic conditions for t-tough graphs
• Closed walks and eigenvalues of abelian Cayley graphs
• Hamiltonian results inK1,3-free graphs
• Interlacing eigenvalues and graphs
• Matchings in regular graphs from eigenvalues
• Not every 2-tough graph is Hamiltonian
• Spectra of graphs
• The complexity of recognizing tough cubic graphs
• The connectivity of strongly regular graphs
• Tough Ramsey graphs without short cycles
• Tough graphs and Hamiltonian circuits.
• Toughness and spectrum of a graph
• Toughness in graphs -- a survey

Cited in

(22)

• Characterizations of spectral radius and toughness of graphs
• Edge-toughness of some regular graphs
• Spanning trees of bounded degree, connectivity, toughness, and the spectrum of a graph
• Vertex cut, eigenvalues, \([a,b]\)-factors and toughness of connected bipartite graphs
• Graph toughness from Laplacian eigenvalues
• Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs.
• Eigenvalues and toughness of regular graphs
• Toughness and spectral radius in graphs
• The toughness of Kneser graphs
• Distance signless Laplacian spectral radius and toughness in graphs with given minimum degree and order
• Toughness in pseudo-random graphs
• A unified combinatorial view beyond some spectral properties
• \(l\)-connectivity, \(l\)-edge-connectivity and spectral radius of graphs
• Toughness, Hamiltonicity and eigenvalues of graphs
• Generalized toughness and spectral radius of graphs
• Eigenvalues, edge-disjoint perfect matchings and toughness of regular graphs
• Sharp spectral bounds for the vertex-connectivity of regular graphs
• Toughness, Hamiltonicity and spectral radius in graphs
• Spectral conditions for connectivity, toughness and perfect k-matchings of regular graphs
• A proof of Brouwer's toughness conjecture
• Toughness and normalized Laplacian eigenvalues of graphs
• Regular graphs. A spectral approach

This page was built for publication: The spectrum and toughness of regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q403562)