Spectrum and Expansion of Biregular Graphs

Citation:

Bélanger-Rioux R, Filip I. Spectrum and Expansion of Biregular Graphs. Delta Epsilon, the McGill Undergraduate Mathematics Journal [Internet]. 2007;(2) :26-29.

Abstract:

Graphs with a strong expansion property are extremely useful in many areas of mathematics and computer science, particularly in the design of efficient algorithms. It is, however, very difficult to explicitly construct infinite families of good expanders. In this paper, we study the spectrum of biregular graphs and show how it is related to their expansion coefficient. We also describe a construction of biregular expanders from elliptic curves. Finally, we present some experimental results on the second largest eigenvalues of biregular graphs with degrees 2 and 7.

Publisher's Version