The line-graph inertia conjecture

Let GG be a connected graph, and let L(G)L(G) denote its line graph. Let n+(L(G))n^+(L(G)) and n(L(G))n^-(L(G)) be the numbers of positive and negative eigenvalues of the adjacency matrix of L(G)L(G), and let s(L(G))s(L(G)) be its signature. Line-graph inertia conjecture.

n+(L(G))n(L(G))+1.n^+(L(G))\leq n^-(L(G))+1.

Equivalently, s(L(G))1s(L(G))\leq 1. The paper proves a weaker upper bound for line graphs and presents computational evidence for this sharper conjecture, which remains open.

Sources & referencesView supporting material

Primary source

Saieed Akbari, Clive Elphick, Hitesh Kumar, Shivaramakrishna Pragada and Quanyu Tang, “A new conjecture on the inertia of graphs”, arXiv:2508.01163 (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.