Disconnecting strongly regular graphs

DOI10.1016/J.EJC.2013.10.008MaRDI QIDQ2637232zbMATHOpenAlexFDO

Authors Sebastian Cioaba, Jack H. Koolen, Weiqiang Li

Publication date 10 February 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Latin square graphsblock graphs of Steiner 2-designsconnected strongly regular graph

Mathematics Subject Classification ID

Association schemes, strongly regular graphs (05E30) Connectivity (05C40)

Abstract: In this paper, we show that the minimum number of vertices whose removal disconnects a connected strongly regular graph into non-singleton components, equals the size of the neighborhood of an edge for many graphs. These include blocks graphs of Steiner $2$-designs, many Latin square graphs and strongly regular graphs whose intersection parameters are at most a quarter of their valency.

Recommendations

• On a conjecture of Brouwer involving the connectivity of strongly regular graphs
• The cyclic edge-connectivity of strongly regular graphs
• Some characterizations of strongly regular graphs with respect to their vertex deleted subgraphs
• Strongly regular graphs with strongly regular decomposition
• The disconnection number of a graph

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• 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 50655 (Why is no real title available?)
• scientific article; zbMATH DE number 1256777 (Why is no real title available?)
• scientific article; zbMATH DE number 1054729 (Why is no real title available?)
• scientific article; zbMATH DE number 2149410 (Why is no real title available?)
• A course in combinatorics.
• A remark on partial linear spaces of girth 5 with an application to strongly regular graphs
• A short proof of the nonexistence of a pair of orthogonal Latin squares of order six
• An isoperimetric problem in Cayley graphs
• Circulants and their connectivities
• Distance regular graphs of diameter 3 and strongly regular graphs
• Extraconnectivity of graphs with large girth
• Extraconnectivity of graphs with large minimum degree and girth
• On Isoperimetric Connectivity in Vertex-Transitive Graphs
• On a conjecture of Brouwer involving the connectivity of strongly regular graphs
• On strongly regular graphs with \(\mu \leq 2\)
• On the extraconnectivity of graphs
• Random strongly regular graphs?
• Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3
• Strongly regular graphs with smallest eigenvalue -m
• 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 strongly regular (45,\,12,\,3,\,3) graphs
• The vertex-connectivity of a distance-regular graph

Cited in

(12)

• The cyclic edge-connectivity of strongly regular graphs
• Recent progress on graphs with fixed smallest adjacency eigenvalue: a survey
• Connectivity concerning the last two subconstituents of a \(Q\)-polynomial distance-regular graph
• The disconnection number of a 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
• On a conjecture of Brouwer involving the connectivity of strongly regular graphs
• Completely Disconnecting the Complete Graph
• An extended chaotic maps-based keyword search scheme over encrypted data resist outside and inside keyword guessing attacks in cloud storage services

This page was built for publication: Disconnecting strongly regular graphs

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