A Generalized Alon-Boppana Bound and Weak Ramanujan Graphs

[摘要] 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

[学科分类] 离散数学和组合数学

[关键词] Eigenvalues;Laplacian;Expander;Ramanujan graphs