×

The combinatorial inverse eigenvalue problems: complete graphs and small graphs with strict inequality. (English) Zbl 1282.05090

Summary: Let \(G\) be a simple undirected graph on \(n\) vertices and let \(S(G)\) be the class of real symmetric \(n \times n\) matrices whose nonzero off-diagonal entries correspond exactly to the edges of \(G\).
Given \(2n-1\) real numbers \(\lambda_1\geq \mu_1\geq \lambda_2\geq \mu_2\geq \dots \geq \lambda_{n-1}\geq \mu_{n-1}\geq \lambda_n\) , and a vertex \(v\) of \(G\), the question is addressed of whether or not there exists \(A\in S(G)\) with eigenvalues \(\lambda_1 ,\dots,\lambda_n\) such that \(A(v)\) has eigenvalues \(\mu_1 ,\dots,\mu_{n-1}\) , where \(A(v)\) denotes the matrix with the \(v\)-th row and column deleted.
General results that apply to all connected graphs \(G\) are given first, followed by a complete answer to the question for \(K_n\) . Since the answer is constructive it can be implemented as an algorithm; a Mathematica code is provided to do so. Finally, for all connected graphs on 4 vertices it is shown that the answer is affirmative if all six inequalities are strict.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A42 Inequalities involving eigenvalues and eigenvectors
15B57 Hermitian, skew-Hermitian, and related matrices

Software:

Mathematica
PDFBibTeX XMLCite
Full Text: Link