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

DOI10.1016/J.JCTA.2012.01.001MaRDI QIDQ765871zbMATH OpenOpenAlexWikidataFDO

Authors Sebastian Cioaba, Kijung Kim, Jack H. Koolen

Publication date 22 March 2012

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1105.0796

zbMATH Keywords

eigenvaluesstrongly regular graphsconnectivitydistance regular graphscopolar spacesdelta spaces

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Association schemes, strongly regular graphs (05E30) Connectivity (05C40)

Abstract: 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.

Recommendations

• Disconnecting strongly regular graphs
• On the strong regularity of some edge-regular graphs
• On the connectedness of the complement of a ball in distance-regular graphs
• The cyclic edge-connectivity of strongly regular graphs
• Strongly regular graphs with \(\lambda\) = 1

Cites work

• scientific article; zbMATH DE number 997668 (Why is no real title available?)
• scientific article; zbMATH DE number 3884175 (Why is no real title available?)
• scientific article; zbMATH DE number 3877205 (Why is no real title available?)
• scientific article; zbMATH DE number 3670480 (Why is no real title available?)
• scientific article; zbMATH DE number 3482588 (Why is no real title available?)
• scientific article; zbMATH DE number 2149410 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• A course in combinatorics.
• A spectral approach to bandwidth and separator problems in graphs
• An isoperimetric problem in Cayley graphs
• CLASSIFYING COPOLAR SPACES AND GRAPHS
• Chromatic number and the 2-rank of a graph
• Classification of regular two-graphs on 36 and 38 vertices
• Distance regular graphs of diameter 3 and strongly regular graphs
• Eigenvalues and expanders
• Explicit Concentrators from Generalized N-Gons
• Finite nets. II: Uniqueness and imbedding
• Interlacing eigenvalues and graphs
• Problems in algebraic combinatorics
• Pseudo-random graphs
• Random strongly regular graphs?
• Simple Lie algebras and graphs
• Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3
• Strongly regular graphs with smallest eigenvalue -m
• Strongly regular graphs, partial geometries and partially balanced designs
• Symplectic graphs and their automorphisms
• The Gewirtz graph: An exercise in the theory of graph spectra
• The connectivity of strongly regular graphs
• The graphs with spectral radius between 2 and \(\sqrt{2+\sqrt{5}}\)
• The vertex-connectivity of a distance-regular graph

Cited in

(8)

• The cyclic edge-connectivity of strongly regular graphs
• Connectivity concerning the last two subconstituents of a \(Q\)-polynomial distance-regular graph
• On the connectivity of graphs in association schemes
• Spectral threshold for extremal cyclic edge-connectivity
• The extendability of matchings in strongly regular graphs
• The edge-connectivity of strongly 3-walk-regular graphs
• Max-cut and extendability of matchings in distance-regular graphs
• Disconnecting strongly regular graphs

This page was built for publication: On a conjecture of Brouwer involving the connectivity of strongly regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q765871)