Maximum spectral gaps of graphs

DOI10.1016/J.LAA.2025.10.024MaRDI QIDQ6894382zbMATH OpenFDO

Authors George Brooks, William Linz, Linyuan Lu

Publication date 25 November 2025

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.LAA.2025.10.024

zbMATH Keywords

extremal graph eigenvalue problemHadamard matriceslinear combination of eigenvalues of graphsspread of graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Inequalities involving eigenvalues and eigenvectors (15A42) Boolean and Hadamard matrices (15B34)

Review text

The authors study the problem of maximizing the difference \(\lambda_{i+1}-\lambda_{n-j}\) for a given pair \((i, j)\) over all graphs on \(n\) vertices. This problem is related with the spread of a graph \(G\) (i.e., the difference \(\lambda_{1}-\lambda_{n}\) between the largest and smallest eigenvalues of its adjacency matrix). They give upper bounds for all pairs \((i, j)\) and exhibit an infinite family of pairs where the bound is tight. In their proof, the key idea is to consider graphs with possible self-loops, not simple graphs.

Cites work

• Extrema of graph eigenvalues
• Improved lower bounds on the extrema of eigenvalues of graphs
• Linear combinations of graph eigenvalues
• Maximum spread of graphs and bipartite graphs
• On the sum of two largest eigenvalues of a symmetric matrix
• The spread of a matrix
• The spread of the spectrum of a graph

This page was built for publication: Maximum spectral gaps of graphs

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