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

Expanding graphs, Ramanujan graphs, and 1-factor perturbations

Authors
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
Identifiers
Full text
Article (Author postprint) (121 Kb) - public document Free access
Structures
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. https://archive-ouverte.unige.ch/unige:12113

171 hits

46 downloads

Update

Deposited on : 2010-10-15

Export document
Format :
Citation style :