A discrete nodal domain theorem for trees (Q1863531)

consider a graph \(G\) on vertices \(1,2,\dots,n\) and a real vector \((x_1,x_2,\dots,x_n)\). A positive (negative) sign graph is a maximal connected subgraph of \(G\) on vertices \(v\) with \(x_v>0\) (\(x_v<0\)). Sign graphs are also called nodal domains. Their number is denoted by \(\eta(x)\). Let \(A\) be a generalized Laplacian of \(G\), that is \(A\) is a symmetric \(n \times n\) matrix and its entries are negative for adjacent vertices and zero for distinct non-adjacent vertices. Consider the eigenvalues \(\lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_n\) of \(A\). \textit{E. B. Davies} et al.\ [Linear Algebra Appl.\ 336, 51-60 (2001; Zbl 0990.05093)] proved that \(\eta(y) \leq k+r-1\) for all eigenvectors \(y\) of \(A\) corresponding with an eigenvalue \(\lambda_k\) of multiplicity \(r\). This discrete nodal domain theorem is strengthened for trees. If \(G\) is a tree and \(y\) is an eigenvector without a vanishing coordinate, then the corresponding eigenvalue \(\lambda_k\) is simple and \(\eta(y)=k\). For multiple eigenvalues more complicated bounds exist. Given a generalized Laplacian \(A\) of a tree and an eigenvalue \(\lambda\) of \(A\) with multiplicity at least \(2\), a corresponding eigenvector \(y\) with maximal \(\eta(y)\) can be found in time \(O(n^2)\). Deciding the corresponding minimization problem is NP-complete.