Note on the girth of Ramanujan graphs
type: Item
instance of: scholarly article
title: Note on the girth of Ramanujan graphs
zbMATH Open document ID: 0708.05032
DOI: 10.1016/0095-8956(90)90026-V
author: A. G. Boshier
author: Norman L. Biggs
published in: Journal of Combinatorial Theory. Series B
publication date: 1990-01-01T00:00:00Z
review text: A Ramanujan graph in a finite k-regular graph all eigenvalues of which, other than \(\pm k\), have modulus at most \(2\sqrt{k-1}\). Such graphs are well-suited for the construction of expanders. \textit{A. Lubotzky, R. Phillips} and \textit{P. Sarnak} [Combinatorica 8, No.3, 261-277 (1988; Zbl 0661.05035)] presented, for infinitely many k, an explicit construction of such graphs with order n and girth g asymptotically satisfying \((\log_{k-1}n)/g\leq 3/4\). The author shows this bound to be sharp.
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4162912
zbMATH Keywords: Ramanujan graph
zbMATH Keywords: eigenvalues
zbMATH Keywords: expanders
zbMATH Keywords: girth
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: The sextet construction for cubic graphs
cites work: Explicit constructions of linear-sized superconcentrators
cites work: Ramanujan graphs
cites work: Explicit constructions of graphs without short cycles and low density codes
cites work: Girths of bipartite sextet graphs
full work available at URL: 0095-8956(90)90026-v
OpenAlex ID: W2073266670
description: scientific article; zbMATH DE number 4162912