Unweighted Nordhaus–Gaddum conjecture for graph inertia

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 n≥0(AH)n_{\geq 0}(A_H) denote the number of nonnegative eigenvalues of AHA_H.

Unweighted Nordhaus–Gaddum conjecture. One has

n≥0(AG) n≥0(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.

References

Primary source

Quanyu Tang, Shengtong Zhang and Clive Elphick, “Inertia, Independence and Expanders”, arXiv:2505.07305 (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.