ELA, Volume 9, pp. 27-31, March 2002, abstract.

Estimation of the maximum multiplicity of an 
eigenvalue in terms of the vertex degrees of 
the graph of a matrix

Charles R. Johnson and Carlos M. Saiago

The maximum multiplicity among eigenvalues of matrices 
with a given graph cannot generally be expressed in 
terms of the degrees of the vertices (even when the 
graph is a tree). Given are best possible lower and
upper bounds, and characterization of the cases of 
equality in these bounds. A by-product is a sequential 
algorithm to calculate the exact maximum multiplicity 
by simple counting.