UNIGE document Scientific Article
previous document  unige:12113  next document
add to browser collection

Expanding graphs, Ramanujan graphs, and 1-factor perturbations

Musitelli, Antoine
Published in Bulletin of the Belgian Mathematical Society - Simon Stevin. 2006, vol. 13, no. 4, p. 673-680
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 graphsRamanujan graphs1-factorsPerturbations
Stable URL https://archive-ouverte.unige.ch/unige:12113
Full text
Article (Author postprint) (121 Kb) - public document Free access

170 hits



Deposited on : 2010-10-15

Export document
Format :
Citation style :