Sebastian Cioaba
University of Delaware

Disconnecting strongly regular graphs

Abstract: In 1986, Brouwer and Mesner proved that the vertex connectivity of any connected strongly regular graph equals its degree and that the only disconnecting sets of minimum size are the neighborhoods of the vertices of the graph. This result was recently extended to distance regular graphs by Brouwer and Koolen. In 1996, Brouwer asked what is the size of a minimum disconnecting set in a strongly regular graphs whose removal creates non-singleton components and conjectured that this equals the size of the neighborhood of an edge. In this talk, I will prove that this is false in general; the counterexamples we have found have an interesting structure and it is an interesting open problem to classify all the counterexamples to this conjecture. I will also prove the conjecture is true in many cases such as Paley graphs for example. This is joint work with Kijung Kim and Jack Koolen from POSTECH, South Korea.