Loading...
research article
Expanding graphs, Ramanujan graphs, and 1-factor perturbations
de la Harpe, Pierre
•
Musitelli, Antoine
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.
Loading...
Name
PRO 060625.pdf
Access type
openaccess
Size
172.99 KB
Format
Adobe PDF
Checksum (MD5)
a0319a557022537c16bfeb92afdcc6c3