Expanding graphs, Ramanujan graphs, and 1-factor perturbations

Simple item page
dc.creatorde la Harpe, Pierre
dc.creatorMusitelli, Antoine
dc.date2005-03-16
dc.date.accessioned2026-07-07T05:18:00Z
dc.date.available2026-07-07T05:18:00Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/math/0503330
dc.identifierhttp://arxiv.org/abs/math/0503330
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/74514
dc.subjectCombinatorics
dc.subject80E25
dc.titleExpanding graphs, Ramanujan graphs, and 1-factor perturbations
dc.typetext

Files

Collections

arXiv