DIMACS TR: 93-83

Isoperimetric Inequalities and Eigenvalues

Author: Nabil Kahale


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