Expanding graphs, Ramanujan graphs, and 1-factor perturbations
de la Harpe, Pierre ; Musitelli, Antoine
Bull. Belg. Math. Soc. Simon Stevin, Tome 12 (2006) no. 5, p. 673-680 / Harvested from Project Euclid
We construct $(k \pm 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\sqrt 5 \approx 1.52$; the corresponding minoration for a sequence of Ramanujan $7$-regular graphs (which is not known to exist) would be $7 - 2\sqrt 6 \approx 2.10$.
Publié le : 2006-12-14
Classification:  Expanding graphs,  Ramanujan graphs,  1-factors,  perturbations,  05C50
@article{1168957343,
     author = {de la Harpe, Pierre and Musitelli, Antoine},
     title = {Expanding graphs, Ramanujan graphs, and 1-factor perturbations},
     journal = {Bull. Belg. Math. Soc. Simon Stevin},
     volume = {12},
     number = {5},
     year = {2006},
     pages = { 673-680},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1168957343}
}
de la Harpe, Pierre; Musitelli, Antoine. Expanding graphs, Ramanujan graphs, and 1-factor perturbations. Bull. Belg. Math. Soc. Simon Stevin, Tome 12 (2006) no. 5, pp.  673-680. http://gdmltest.u-ga.fr/item/1168957343/