DIMACS TR: 93-83
Isoperimetric Inequalities and Eigenvalues
Author: Nabil Kahale
ABSTRACT
An upper bound is given on the minimum distance between $i$ subsets
of the same size of a regular graph in terms of the $i$-th largest
eigenvalue in absolute value. This yields a bound on the diameter in
terms of the $i$-th largest eigenvalue, for any integer $i$. Our
bounds are shown to be asymptotically tight. A recent result by
Quenell relating the diameter, the second eigenvalue, and the girth
of a regular graph is obtained as a byproduct.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-83.ps
DIMACS Home Page