Expanding graphs, Ramanujan graphs, and 1-factor perturbations

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 6−2√5 ≈ 1.52; the corresponding minoration for a sequence of Ramanujan 7- regular graphs (which is not known to exist) would be 7 − 2√6 ≈ 2.10.


Published in:
Bulletin of the Belgian Mathematical Society, 13, 4, 673-680
Year:
2006
Keywords:
Note:
PRO 060602
Laboratories:




 Record created 2007-02-02, last modified 2018-10-01

n/a:
Download fulltextPDF
External link:
Download fulltextURL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)