The change in multiplicity of an eigenvalue due to adding or removing edges (Q1625481)

Let \(G\) be a simple, undirected graph on \(n\) vertices and denote by \( \mathcal{H}(G)\) the set of all \(n\times n\) Hermitian matrices, the graph of whose off-diagonal entries is \(G\) (no restriction is placed on the diagonal entries). For \(A\in \mathcal{H}(G)\), let \(m_{A}(\lambda )\) and \(\sigma (A)\) denote the multiplicity of an eigenvalue \(\lambda \) of \(A\) and the spectrum of \(A,\) respectively. When a vertex \(u\) is removed from \(G\), the remaining graph is denoted by \(G(u)\) and \(A(u)\in \mathcal{H}(G(u))\) denotes the \( (n-1)\times (n-1)\) submatrix of \(A\in \) \(\mathcal{H}(G)\) resulting from deletion of the row and the column corresponding to \(u\). It is known (see [\textit{R. A. Horn} and \textit{C. R. Johnson}, Matrix analysis. 2nd ed. Cambridge: Cambridge University Press (2013; Zbl 1267.15001)]) that for \(A\in \) \(\mathcal{H}(G)\), \(A(u)\in \mathcal{ H}(G(u))\), and \(\lambda \in \sigma (A)\), the multiplicity of \(\lambda \) may change at most \(1\) when the vertex \(u\) is deleted. A vertex \(u\) of a graph \( G \) is called ``Parter'' (respectively, ``neutral'', ``downer'') in \(G\) for an eigenvalue \(\lambda \) of \(A\in \) \(\mathcal{H}(G),\) relative to matrix \(A\), if \[ m_{A(u)}(\lambda )=m_{A}(\lambda )+1 \] (respectively, \(m_{A(u)}(\lambda )=m_{A}(\lambda ),\text{ }m_{A(u)}(\lambda )=m_{A}(\lambda )-1)\). These numbers define the status of the vertex \(u\) for the eigenvalue \(\lambda \) relative to \(A\). Given a graph \(G\) and \(A\in \mathcal{H}(G)\), the authors first investigate in Section 2 the change of multiplicity of an eigenvalue \(\lambda \) of \(A\) when edges are inserted into \(G\). One of the results of Subsection 2.1 follows: Let \(A\in \mathcal{H}(G)\) and let \(v\) be a Parter vertex in \(G\) for \(\lambda \in \sigma (A)\). When edges are inserted between \(v\) and other vertices, let the resulting graph be \(\widehat{G}\), and let \(\widehat{A}\in \mathcal{H}( \widehat{G})\) be the same as \(A\) except for the new edges in \(\widehat{G}\). Then \(m_{\widehat{A}}(\lambda )=m_{A}(\lambda )\) if and only if \(v\) is a Parter vertex in \(\widehat{G}\) for \(\lambda \in \sigma \left( \widehat{A} \right) \). In Subsection 2.2, the authors study changes in the multiplicity of eigenvalues when two disjoint graphs are connected with an edge, based upon the statuses of the two vertices that are connected. They for example prove the following result: Let \(G_{1}\) and \(G_{2}\) be disjoint graphs and let \(A\in \mathcal{H}(G_{1})\) and \(B\in \mathcal{H}(G_{2})\). Let \(G\) be a graph obtained by inserting an edge between the vertex \(u_{1}\) of \(G_{1}\) and \(u_{2}\) of \(G_{2}\). Let \(C\in \mathcal{H}(G)\) be such that the principal submatrices corresponding to \( G_{1}\) and \(G_{2}\) are \(A\) and \(B\), respectively. If \(u_{1}\) is Parter in \( G_{1}\) for \(\lambda \in \sigma (C)\) relative to \(A\in \mathcal{H}(G_{1})\) (or \(u_{2}\) is Parter in \(G_{2}\) for \(\lambda \in \sigma (C)\) relative to \( B\in \mathcal{H}(G_{2})\)), then \(m_{C}(\lambda )=m_{A}(\lambda )+m_{B}(\lambda )\) and \(u_{1}\) (or \(u_{2}\)) is still Parter in \(G\) for \( \lambda \). In Section 3, the authors consider the inverse operation of edge removal and study cases in which the multiplicity does not change due to removing edges in a graph. Finally, in the last section, possible classifications of cut-edges in a graph are given and necessary and sufficient conditions for each classification are presented.