The Nordhaus–Gaddum full Brouwer conjecture for Laplacian spectra

Let GG be a graph with nn vertices, let G\overline{G} be its complement, and let sk(G)s_k(G) denote the sum of the kk largest Laplacian eigenvalues of GG. Nordhaus–Gaddum full Brouwer conjecture. For every k{1,2,,n1}k\in\{1,2,\cdots,n-1\},

sk(G)+sk(G)(n2)+2(k+12),s_k(G)+s_k(\overline{G})\leq\binom{n}{2}+2\binom{k+1}{2},

with equality if and only if GG is a threshold graph having n=2k+1n=2k+1 vertices and clique number k+1k+1. This is proposed as a Nordhaus–Gaddum analogue of the full Brouwer conjecture; the source presents only partial solutions, so the general assertion remains open.

Sources & referencesView supporting material

Primary source

Xiaodan Chen and Junwei Zi, “More on the full Brouwer Laplacian spectrum conjecture”, arXiv:2503.11165 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.