A generalized Alon-Boppana bound and weak Ramanujan graphs

Fan Chung¹

¹University of California San Diego

The electronic journal of combinatorics, Tome 23 (2016) no. 3

Résumé

A basic eigenvalue bound due to Alon and Boppana holds only for regular graphs. In this paper we give a generalized Alon-Boppana bound for eigenvalues of graphs that are not required to be regular. We show that a graph $G$ with diameter $k$ and vertex set $V$, the smallest nontrivial eigenvalue $\lambda_1$ of the normalized Laplacian $\mathcal L$ satisfies$$ \lambda_1 \leq 1-\sigma \big(1- \frac c {k} \big)$$ for some constant $c$ where $\sigma = 2\sum_v d_v \sqrt{d_v-1}/\sum_v d_v^2 $ and $d_v$ denotes the degree of the vertex $v$.We consider weak Ramanujan graphs defined as graphs satisfying $ \lambda_1 \geq 1-\sigma$. We examine the vertex expansion and edge expansion of weak Ramanujan graphs and then use the expansion properties among other methods to derive the above Alon-Boppana bound. A corrigendum was added on the 3rd of November 2017.

Détail

DOI : 10.37236/5933

Classification : 05C50
Mots-clés : eigenvalues, Laplacian, expander, Ramanujan graphs