The normalized algebraic-connectivity Nordhaus-Gaddum conjecture

Let GG be a graph on nn vertices, let GcG^c be its complement, and let λ2(G)\lambda_2(G) denote the second-smallest eigenvalue of the normalized Laplacian of GG.

Normalized algebraic-connectivity conjecture.

λ2(G)+λ2(Gc)2O(1n).\lambda_2(G)+\lambda_2(G^c)\leq 2-O\left(\frac{1}{\sqrt{n}}\right).

The conjecture is motivated by focus graphs, for which the two normalized algebraic connectivities approach 11 while their sum approaches 22. The supplied text does not provide a proof, disproof, or further resolution.

Sources & referencesView supporting material

Primary source

Mark Kempton, Xavier Zaitzeff and Sibi Muthuprakash, “Nordhaus-Gaddum upper bounds for graph connectivity parameters”, arXiv:2606.12751 (2026).

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.