Graphs sharing an arbitrary number of ordered complementarity eigenvalues (Q6136672)

Let \(A\) be a real matrix of order \(n\). A real number \(\lambda\) is called a complementary eigenvalue of \(A\) if there exists a nonzero vector \(\mathfrak{x}\in\mathbb{R}^n\) such that \[ \mathfrak{x}\geq 0, \quad A\mathfrak{x}-\lambda\mathfrak{x}\geq 0,\quad \mathfrak{x}^\top(A\mathfrak{x}-\lambda\mathfrak{x})=0, \] where \(\mathfrak{x}\geq 0\) means that every entry of vector \(\mathfrak{x}\) is non-negative. The complementary spectrum of \(G\) is the set of distinct complementary eigenvalues of its adjacency matrix. Alternatively, the complementary spectrum of a graph is a finite collection of the different spectral radii of all induced subgraphs, where for a given graph \(G\), the spectral radius is the largest eigenvalue of the adjacency matrix \(A(G)\). The separability index of a class \(\mathcal{G}\) of connected graphs is the minimal number of successive complementary eigenvalues, starting from the largest one, that is needed to separate \(\mathcal{G}\). The main result of the paper shows that for each \(n\geq 15\) there is a pair of connected graphs sharing their \(n-13\) largest complementary eigenvalues but the \(n-12\) largest are different. Therefore, the separability index of such a pair is equal to \(n-12\). In addition, it follows that the separability index of the class of all connected graphs cannot be a constant.