2005/03/16 by Pierre de la Harpe, de la Harpe, Pierre, Antoine Musitelli +1
Computer Science · Mathematics · #80E25 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:80E25
paper · pdf · doi:10.48550/arxiv.math/0503330
arxiv created 2005/03/16 · openalex publication_date 2005/03/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.