Tight Estimates for Eigenvalues of Regular Graphs

A. Nilli


It is shown that if a $d$-regular graph contains $s$ vertices so that the distance between any pair is at least $4k$, then its adjacency matrix has at least $s$ eigenvalues which are at least $2 \sqrt {d-1} \cos \big({\pi\over 2 k}\big)$. A similar result has been proved by Friedman using more sophisticated tools.

Full Text: