Unweighted Nordhaus–Gaddum conjecture for graph inertia

From papers

Let GG be a connected graph on nn vertices, and let G\overline{G} denote its complement. For a graph HH, let AHA_H be its unweighted adjacency matrix, and let n0(AH)n_{\geq 0}(A_H) denote the number of nonnegative eigenvalues of AHA_H.

Unweighted Nordhaus–Gaddum conjecture. One has

n0(AG)n0(AG)n.n_{\geq 0}(A_G)\,n_{\geq 0}(A_{\overline{G}})\geq n.

The multiplicative Nordhaus–Gaddum inequality is proposed here for unweighted inertia after the corresponding weighted inequality is shown not to hold in its natural form. The additive inequality is known, but the multiplicative bound remains open according to the source.

Progress summary

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

Sources & referencesView supporting material

Primary source

Quanyu Tang, Shengtong Zhang and Clive Elphick, “Inertia, Independence and Expanders”, arXiv:2505.07305 (2025).

Solutions 0

No solutions have been posted yet.