Counterexamples to a conjecture on graph inertia

Abstract

The inertia of a graph $G$ is $\mathrm{In}(G)=(n^{+}(G),n^0(G),n^{-}(G))$, where $n^{+}(G),n^0(G),n^{-}(G)$ are the numbers of positive, zero and negative eigenvalues of the adjacency matrix of $G$, respectively, counted with multiplicities. Akbari, Elphick, Kumar, Pragada and Tang [Discrete Math. 349 (2026) 114953] conjectured that every graph $G$ satisfies \[ 2n^+(G)\le n^-(G)(n^-(G)+1). \] In this note, we construct a family of reduced graphs $\{W_k:k\ge 5\}$ with \[ \operatorname{In}(W_k) = \left(\binom{k}{2}+1,\ 0,\ k-1\right), \] each of which violates the conjectured inequality. We also observe that deleting the vertex $a_1$ from $W_5$ gives a reduced graph with inertia $(10,0,4)$, answering a question raised in the same paper. The family also refutes a weaker inequality proposed there.

9 pages. Any comments and suggestions are welcome