Expanding graphs, Ramanujan graphs, and 1-factor perturbations

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 t...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2005-03
Main Authors: de la Harpe, Pierre, Musitelli, Antoine
Format: Article
Language:English
Subjects:
Expanders
Fields (mathematics)
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422