Seminar - Sebi Ciaoba

Connectivity and matching properties of distance-regular graphs

Abstract:

A strongly regular graph is a regular graph such that the size of the common neighborhood of two distinct vertices depends only on whether the vertices are adjacent or not. A primitive strongly regular graph is a strongly regular graph that is not a union of cliques or a complete multipartite graph. The second subconstituent of a strongly regular graph G with respect to a vertex x, is the subgraph of G induced by the vertices at distance 2 from x. An important property of primitive strongly regular graphs is the fact that the second subconstituent of any vertex is connected. In 2011, at GAC5, Andries Brouwer asked to what extent can this statement be generalized to distance-regular graphs? I will discuss our progress on this problem. This is joint work with Jack Koolen.

A graph is called t-extendable if it has even order and any matching of size t is contained in a perfect matching. The extendability of a graph is the maximum t such that the graph is t-extendable. In 1980s, Holton studied the extendability of strongly regular graphs. I will present some recent results regarding the extendability of strongly regular graphs and distance-regular graphs. This is joint work with Jack Koolen and Weiqiang Li.