PreprintarXiv licencearXiv
Generalized Nordhaus--Gaddum Inequalities for Eigenvalues
Abstract
For a graph G, let $ λ_1(G)\ge λ_2(G)\ge \cdots \ge λ_n(G)$ denote the adjacency eigenvalues of G. We prove that for all looped graphs G on n vertices, λ1(G) + λ2(G̅) ≤ 8/7 n. Our method also gives a short new proof of the Nordhaus-Gaddum result for the spectral radius proved by Terpai that λ1(G) + λ1(G̅) ≤ 4/3n − 1. We investigate the asymptotic maximum of λi(G)+λj(G̅) for fixed i and j. We prove general bounds on λi(G) + λj(G̅) for all pairs $(i, j)$ and also give general bounds on the related problem of minimizing λn−i+1(G) + λn−j+1(G̅) for fixed i and j. We also show the close relation of these Nordhaus-Gaddum type problems to recent work on the maximum spectral gaps of graphs by Brooks, Linz and Lu.
Related
- On the Burning Game: Nordhaus-Gaddum Bounds and Graph Products
- Inequalities between Dirichlet and Neumann eigenvalues in large dimensions
- Scaling inequalities and limits for clamped plate eigenvalues on geodesic disks
- Quadratic inequalities between the largest eigenvalues of a graph
- Generalized principal eigenvalues for nonlocal operators with drift
BibTeX
@misc{agarwal2026generalized,
title = {{Generalized Nordhaus--Gaddum Inequalities for Eigenvalues}},
author = {Sahil Agarwal and Carter Antley and Joseph Aulenbacher and George Brooks and Ian Gonzalez and Luke Hawranick and William Linz and Linyuan Lu and Aiden Williams},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.15941},
eprint = {2607.15941},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.15941},
}
RIS
TY - UNPB
TI - Generalized Nordhaus--Gaddum Inequalities for Eigenvalues
AU - Sahil Agarwal
AU - Carter Antley
AU - Joseph Aulenbacher
AU - George Brooks
AU - Ian Gonzalez
AU - Luke Hawranick
AU - William Linz
AU - Linyuan Lu
AU - Aiden Williams
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2607.15941
UR - https://arxiv.org/abs/2607.15941
AB - For a graph G, let $ λ_1(G)\ge λ_2(G)\ge \cdots \ge λ_n(G)$ denote the adjacency eigenvalues of G. We prove that for all looped graphs G on n vertices, λ_1(G) + λ_2(G̅) ≤ 8/7 n. Our method also gives a short new proof of the Nordhaus-Gaddum result for the spectral radius proved by Terpai that λ_1(G) + λ_1(G̅) ≤ 4/3n − 1. We investigate the asymptotic maximum of λ_i(G)+λ_j(G̅) for fixed i and j. We prove general bounds on λ_i(G) + λ_j(G̅) for all pairs $(i, j)$ and also give general bounds on the related problem of minimizing λ_n−i+1(G) + λ_n−j+1(G̅) for fixed i and j. We also show the close relation of these Nordhaus-Gaddum type problems to recent work on the maximum spectral gaps of graphs by Brooks, Linz and Lu.
ER -