Ramanujan graphs

A. Lubotzky, R. Phillips, P. Sarnak

Research output: Contribution to journalArticlepeer-review

1046 Scopus citations


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 logk-1 |X| which gives larger girth than was previously known by explicit or non-explicit constructions.

Original languageEnglish (US)
Pages (from-to)261-277
Number of pages17
Issue number3
StatePublished - Sep 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Discrete Mathematics and Combinatorics


  • AMS subject classification (1980): 05C35


Dive into the research topics of 'Ramanujan graphs'. Together they form a unique fingerprint.

Cite this