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

Speaker  Sebastian Cioaba

Host  Alexandra Kolla

Affiliation  University of Delaware

Duration  00:47:58

Date recorded  27 May 2011

In this paper, we study a conjecture of Andries E. Brouwer from 1996 regarding the minimum number of vertices of a strongly regular graph whose removal disconnects the graph into non-singleton components. We show that the triangular graphs T(m), the symplectic graphs Sp(2r,q) over the field mathbb Fq (for any q prime power), and the strongly regular graphs constructed from the hyperbolic quadrics O+(2r,2) and from the elliptic quadrics O-(2r,2) over the field mathbb F2, respectively, are counterexamples to Brouwer's Conjecture. We prove that Brouwer's Conjecture is true for many families of strongly regular graphs including the conference graphs, the generalized quadrangles GQ(q,q) graphs, the lattice graphs, the Latin square graphs, the strongly regular graphs with smallest eigenvalue -2 (except the triangular graphs) and the primitive strongly regular graphs with at most 30 vertices except for few cases.

©2011 Microsoft Corporation. All rights reserved.
> On a conjecture of Brouwer regarding the connectivity of strongly regular graphs