Article,

Ramanujan Graphs

, , and .
Combinatorica, 8 (3): 261--277 (1988)
DOI: 10.1007/BF02126799

Abstract

A large family of explicit $k$-regular Cayley graphs $X$ is presented. These graphs satisfy a number of extremal combinatorial properties. (i) For eigenvalues $λ$ of $X$ either $λ=±k$ or $|λ| ≦ 2 k−1$. This property is optimal and leads to the best known explicit expander graphs. (ii) The girth of $X$ is asymptotically $≧ 4/3 łog_k−1 |X|$ which gives larger girth than was previously known by explicit or non-explicit constructions.

Tags

Users

  • @ytyoun

Comments and Reviews