Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Sebastian Cioaba

University of Delaware

On a conjecture of Brouwer regarding the connectivity of strongly regular graphs

Abstract:

A $(v,k,\lambda,\mu)$-strongly regular graph (SRG for short) is a finite undirected graph without loops or multiple edges such that (i) it has $v$ vertices, (ii) it is regular of degree $k$, (iii) each edge is in $\lambda$ triangles, (iv) any two nonadjacent points are joined by $\mu$ paths of length 2. The connectivity of a graph is the minimum number of vertices one has to remove in order to make it disconnected (or empty). In 1985, Brouwer and Mesner used Seidel's characterization of strongly regular graphs with eigenvalues at least $-2$ to prove that the vertex-connectivity of any $(v,k,\lambda,\mu)$-SRG equals its degree $k$. Also, they proved that the only disconnecting sets of size $k$ are the neighborhoods $N(x)$ of a vertex $x$ of the graph. A natural question is what the minimum number of vertices whose removal will disconnect a $(v,k,\lambda,\mu)$-SRG into non-singleton components. In 1996, Brouwer conjectured that this number is $2k-\lambda-2$. In this talk, I will report some progress on this problem. This is joint work with Kijung Kim and Jack Koolen (POSTECH, South Korea).

Host: Jacques Verstraete

March 29, 2011

4:00 PM

AP&M 7321

****************************