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.