Algebraic Graph Theory - Sabrina Lato

Title: Distance-Regular and Distance-Biregular Graphs

Abstract: For a given diameter d and valency k, what is the maximum number of vertices a k-regular graph of diameter d can have, and what graphs meet that bound? Although there is a straightforward counting argument to bound the number of vertices using the structural information, the problem of characterizing the graphs that meet the bound turns out to be a problem in algebraic graph theory, and helps gives rise to the notion of distance-regular graphs. A similar problem for bipartite graphs similarly gives rise to the notion of distance-biregular graphs. Motivated by these extremal examples, in this talk we will give a brief introduction to the theory of distance-regular graphs, and how it extends to distance-biregular graphs. We will look at distance-regular and distance-biregular graphs through the framework of sequences of orthogonal polynomials with combinatorial interpretations. No knowledge of algebraic graph theory is assumed.