Some observations on the smallest adjacency eigenvalue of a graph

DOI10.7151/dmgt.2285zbMath1433.05189arXiv1912.03957WikidataQ126413325 ScholiaQ126413325MaRDI QIDQ2295999

Randall J. Elzinga, Sebastian M. Cioabă, David A. Gregory

Publication date: 17 February 2020

Published in: Discussiones Mathematicae. Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

maximum cut; adjacency matrix; smallest eigenvalue; clique partition; graph decomposition; claw-free graphs; graph spectrum

Mathematics Subject Classification ID

05E30: Association schemes, strongly regular graphs

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

15A18: Eigenvalues, singular values, and eigenvectors

05C75: Structural characterization of families of graphs

05C76: Graph operations (line graphs, products, etc.)

Related Items

Adjacency matrices over a finite prime field and their direct sum decompositions, Sharp bounds on the least eigenvalue of a graph determined from edge clique partitions, Spectral radius and clique partitions of graphs, Recent progress on graphs with fixed smallest adjacency eigenvalue: a survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spectra of graphs
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Graphs for which the least eigenvalue is minimal. I
• Graphs for which the least eigenvalue is minimal. II.
• The spectral radius of subgraphs of regular graphs
• Eigenvalues and expanders
• Character sums and abelian Ramanujan graphs (with an appendix by Keqin Feng and Wen-Ch'ing Winnie Li)
• On graphs whose least eigenvalue exceeds \(-1-\sqrt2\)
• Graphs with least eigenvalue \(-2\): a new proof of the 31 forbidden subgraphs theorem
• The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters
• Fractional decompositions and the smallest-eigenvalue separation
• The spectral radius and the maximum degree of irregular graphs
• On the extreme eigenvalues of regular graphs.
• Strongly regular graphs, partial geometries and partially balanced designs
• Eigenvalues of K1,k-Free Graphs and the Connectivity of Their Independence Complexes
• Mixing Rates of Random Walks with Little Backtracking
• Erdős–Ko–Rado Theorems: Algebraic Approaches
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• Generalized line graphs
• Clique coverings of graphs V: maximal-clique partitions
• On the Shannon capacity of a graph
• How Good is the Goemans--Williamson MAX CUT Algorithm?
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Max Cut and the Smallest Eigenvalue
• Bipartite Subgraphs and the Smallest Eigenvalue