en
Scientific article
Open access
English

Expanding graphs, Ramanujan graphs, and 1-factor perturbations

Published inBulletin of the Belgian Mathematical Society Simon Stevin, vol. 13, no. 4, p. 673-680
Publication date2006
Abstract

We construct (k+-1)-regular graphs which provide sequences of expanders by adding or substracting appropriate 1-factors from given sequences of k-regular graphs. We compute numerical examples in a few cases for which the given sequences are from the work of Lubotzky, Phillips, and Sarnak (with k-1 the order of a finite field). If k+1 = 7, our construction results in a sequence of 7-regular expanders with all spectral gaps at least about 1.52.

Keywords
  • Expanding graphs
  • Ramanujan graphs
  • 1-factors
  • Perturbations
Classification
  • arxiv : math.CO
Citation (ISO format)
DE LA HARPE, Pierre, MUSITELLI, Antoine. Expanding graphs, Ramanujan graphs, and 1-factor perturbations. In: Bulletin of the Belgian Mathematical Society Simon Stevin, 2006, vol. 13, n° 4, p. 673–680.
Main files (1)
Article (Accepted version)
accessLevelPublic
Identifiers
ISSN of the journal1370-1444
460views
121downloads

Technical informations

Creation10/13/2010 8:49:00 AM
First validation10/13/2010 8:49:00 AM
Update time03/14/2023 4:07:32 PM
Status update03/14/2023 4:07:32 PM
Last indexation08/28/2023 7:49:37 PM
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack