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

DOI10.1016/J.JCTA.2012.01.001zbMATH Open1241.05149arXiv1105.0796OpenAlexW1881326960WikidataQ123265839 ScholiaQ123265839MaRDI QIDQ765871FDOQ765871

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)

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.

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

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

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)

Cites Work

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

Cited In (9)

• The cyclic edge-connectivity of strongly regular graphs
• The extendability of matchings in strongly regular graphs
• Connectivity concerning the last two subconstituents of a \(Q\)-polynomial distance-regular graph
• A problem of Shapozenko on Johnson graphs
• The edge-connectivity of strongly 3-walk-regular graphs
• On the connectivity of graphs in association schemes
• Spectral threshold for extremal cyclic edge-connectivity
• Disconnecting strongly regular graphs
• Max-cut and extendability of matchings in distance-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)