{"id":"arxiv/2607.15941","url":"https://arxiv.org/abs/2607.15941","tags":["math.CO"],"score":0,"title":"Generalized Nordhaus--Gaddum Inequalities for Eigenvalues","domain":"math.CO","source":"arxiv","authors":["Sahil Agarwal","Carter Antley","Joseph Aulenbacher","George Brooks","Ian Gonzalez","Luke Hawranick","William Linz","Linyuan Lu","Aiden Williams"],"reviews":0,"subject":"math.CO","summary":"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(\\overline{G}) \\le \\frac87 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(\\overline{G}) \\le \\frac43n - 1$. We investigate the asymptotic maximum of \\[ λ_i(G)+λ_j(\\overline G) \\] for fixed $i$ and $j$. We prove general bounds on $λ_i(G) + λ_{j}(\\overline{G})$ for all pairs $(i, j)$ and also give general bounds on the related problem…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-17","reactions":{}}