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 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 of minimizing $λ_{n-i+1}(G) + λ_{n-j+1}(\overline{G})$ for fixed $i$ and $j$. We prove that for all looped graphs $G$ on $n$ vertices, \[λ_1(G) + λ_2(\overline{G}) \le \frac87 n. \] Our method also gives a new short proof of the Nordhaus-Gaddum result for the spectral radius proved by Terpai that $λ_1(G) + λ_1(\overline{G}) \le \frac43n - 1$. 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.

Disclosure

“or 8. Similarly, G2 has 13 vertices and each of them has degree either 6 or 7. From the matrix perspective, this means that each row of the adjacency matrices has as close as possible to the same number of ones and zeros. Acknowledgement ChatGPT 5.5 was used to help with several of the computations. ChatGPT 5.5 Pro also generated the proof idea for a special case of Lemma 16. All of the writing was done by the authors, and we take full responsibility for the contents of the paper.”

PDF page 13

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T18:57:00.632530Z

Structural counts