Algebraic Graph Theory Seminar - Sabrina Lato

Monday, April 26, 2021 11:30 am - 11:30 am EDT (GMT -04:00)

Title: A Spectral Moore Bound for Bipartite Semiregular Graphs

Speaker: Sabrina Lato
Affiliation: University of Waterloo
Zoom: Contact Soffia Arnadottir

Abstract:

The Moore bound provides an upper bound on the number of vertices of a regular graph with a given degree and diameter, though there are disappointingly few graphs that achieve this bound. Thus, it is interesting to ask what additional information can be used to give Moore-type bounds that are tight for a larger number of graphs. Cioaba, Koolen, Nozaki, and Vermette considered regular graphs with a given second-largest eigenvalue, and found an upper bound for such graphs. When the bound is tight, the resulting graph is a distance regular graph of a particular form. Subsequently, Cioaba, Koolen, and Nozaki improved the bound for regular bipartite graphs. In this talk, we will give an overview of some of the techniques used for these proofs and show how they can be applied to give a new bound on the number of vertices in a semiregular graph with a given second-largest eigenvalue. We will also discuss distance biregular graphs, since this relaxation of distance regularity is necessary for the bound to be tight.