Some observations on the smallest adjacency eigenvalue of a graph

DOI10.7151/dmgt.2285zbMath1433.05189arXiv1912.03957OpenAlexW2997909010WikidataQ126413325 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 cutadjacency matrixsmallest eigenvalueclique partitiongraph decompositionclaw-free graphsgraph spectrum

Mathematics Subject Classification ID

Association schemes, strongly regular graphs (05E30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Related Items (4)

Spectral radius and clique partitions of graphs ⋮ 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 ⋮ 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

This page was built for publication: Some observations on the smallest adjacency eigenvalue of a graph