THE COMBINATORIAL INVERSE EIGENVALUE PROBLEM II: ALL CASES FOR SMALL GRAPHS∗

Abstract. Let G be a simple undirected graph on n vertices and let S(G) be the class of real symmetric n × n matrices whose nonzero off-diagonal entries correspond to the edges of G. Given 2n − 1 real numbers λ1 ≥ µ1 ≥ λ2 ≥ µ2 ≥ · · · ≥ λn−1 ≥ µn−1 ≥ λn, and a vertex v of G, the question is addressed of whether or not there exists A ∈ S(G) with eigenvalues λ1,..., λn such that A(v) has eigenvalues µ1,..., µn−1, where A(v) denotes the matrix with vth row and column deleted. A complete solution can be given for the path on n vertices with v a pendant vertex and also for the star on n vertices with v the dominating vertex. The main result is a complete solution to this "λ, µ " problem for all connected graphs on 4 vertices. Key words. Interlacing inequalities, Inverse eigenvalue problem, Symmetric matrix. AMS subject classifications. 05C50, 15A42, 15B57