On the multiplicity of the eigenvalues of a graph

Abstract

Given a graph G with characteristic polynomial p(t), we consider the ML-decomposition p(t) = q(1)(t)q(2)(t)(2) ... q(m)(t)(m), where each q(i)(t) is an integral polynomial and the roots of p(t) with multiplicity j are exactly the roots of q(j)(t). We give an algorithm to construct the polynomials q(i)(t) and describe some relations of their coefficients with other combinatorial invariants of G. In particular, we get new bounds for the energy E(G) = Sigma(n)(i=1) vertical bar lambda(i)vertical bar of G, where lambda(1), lambda(2), ..., lambda(n) are the eigenvalues of G (with multiplicity). Most of the results are proved for the more general situation of a Hermitian matrix whose characteristic polynomial has integral coefficients.