Unweighted Nordhaus–Gaddum conjecture for graph inertia
Unweighted Nordhaus–Gaddum conjecture for graph inertia
Let be a connected graph on vertices, and let denote its complement. For a graph , let be its unweighted adjacency matrix, and let denote the number of nonnegative eigenvalues of .
Unweighted Nordhaus–Gaddum conjecture. One has
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
Sign in to submit a solution.
No solutions have been posted yet.