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

Details On a conjecture of Brouwer involving the connectivity of strongly regular graphs On a conjecture of Brouwer involving the connectivity of strongly regular graphs

2011-05-04

arxiv.org/abs/1105.0796v2

Mathematics

Combinatorics

25 pages, 1 table; accepted to JCTA; revised version contains a new section on copolar and Delta spaces

Scientific paper

10.1016/j.jcta.2012.01.001

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 strongly regular graphs constructed from copolar spaces and from the more general spaces called $\Delta$-spaces are counterexamples to Brouwer's Conjecture. Using J.I. Hall's characterization of finite reduced copolar spaces, we find that the triangular graphs $T(m)$, the symplectic graphs $Sp(2r,q)$ over the field $\mathbb{F}_q$ (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{F}_2$, respectively, are counterexamples to Brouwer's Conjecture. For each of these graphs, we determine precisely the minimum number of vertices whose removal disconnects the graph into non-singleton components. While we are not aware of an analogue of Hall's characterization theorem for $\Delta$-spaces, we show that complements of the point graphs of certain finite generalized quadrangles are point graphs of $\Delta$-spaces and thus, yield other 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. We leave as an open problem determining the best general lower bound for the minimum size of a disconnecting set of vertices of a strongly regular graph, whose removal disconnects the graph into non-singleton components.

Affiliated with

Also associated with

No associations

Rating

On a conjecture of Brouwer involving the connectivity of strongly regular graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On a conjecture of Brouwer involving the connectivity of strongly regular graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On a conjecture of Brouwer involving the connectivity of strongly regular graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-689460