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

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.

Speaker Details

Sebastian Cioaba finished his undergraduate studies in math and computer science at the University of Bucharest, Romania in 2000. He obtained his Ph.D. in 2005 at Queen’s University at Kingston, Canada and was an NSERC PostDoctoral Fellow at the University of California, San Diego (2006-June, 2008 with Fan Chung as a mentor) and University of Toronto (June-December 2008 with Mike Molloy as a mentor). Since January 2009, Sebastian Cioaba is a tenure-track assistant professor at University of Delaware. His research interests are spectral graph theory, extremal combinatorics and their applications.

Date:
Speakers:
Sebastian Cioaba
Affiliation:
University of Delaware

    • Portrait of Jeff Running

      Jeff Running