The line-graph inertia conjecture

About 1 year old · traced to

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.

References

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.