Speaker Sebastian Cioaba
Host Alexandra Kolla
Affiliation University of Delaware
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.