Disconnecting strongly regular graphs

DOI10.1016/J.EJC.2013.10.008zbMATH Open1282.05216arXiv1311.5634OpenAlexW2069135807MaRDI QIDQ2637232FDOQ2637232

Authors: Sebastian Cioaba, Jack H. Koolen, Weiqiang Li 

Publication date: 10 February 2014

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

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.

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

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

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)

Cites Work

• A course in combinatorics.
• Title not available (Why is that?)
• Distance regular graphs of diameter 3 and strongly regular graphs
• The graphs with spectral radius between 2 and \(\sqrt{2+\sqrt{5}}\)
• Extraconnectivity of graphs with large girth
• On the extraconnectivity of graphs
• Circulants and their connectivities
• The Gewirtz graph: An exercise in the theory of graph spectra
• Title not available (Why is that?)
• Strongly regular graphs with smallest eigenvalue -m
• Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3
• Title not available (Why is that?)
• On a conjecture of Brouwer involving the connectivity of strongly regular graphs
• A remark on partial linear spaces of girth 5 with an application to strongly regular graphs
• Title not available (Why is that?)
• Extraconnectivity of graphs with large minimum degree and girth
• Title not available (Why is that?)
• The vertex-connectivity of a distance-regular graph
• The connectivity of strongly regular graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random strongly regular graphs?
• The strongly regular (45,\,12,\,3,\,3) graphs
• A short proof of the nonexistence of a pair of orthogonal Latin squares of order six
• On strongly regular graphs with \(\mu \leq 2\)
• An isoperimetric problem in Cayley graphs
• On Isoperimetric Connectivity in Vertex-Transitive Graphs

Cited In (13)

• The cyclic edge-connectivity of strongly regular graphs
• The extendability of matchings in strongly regular graphs
• An extended chaotic maps-based keyword search scheme over encrypted data resist outside and inside keyword guessing attacks in cloud storage services
• Connectivity concerning the last two subconstituents of a \(Q\)-polynomial distance-regular graph
• A problem of Shapozenko on Johnson graphs
• On a conjecture of Brouwer involving the connectivity of strongly regular graphs
• The edge-connectivity of strongly 3-walk-regular graphs
• Recent progress on graphs with fixed smallest adjacency eigenvalue: a survey
• The disconnection number of a graph
• On the connectivity of graphs in association schemes
• Spectral threshold for extremal cyclic edge-connectivity
• Max-cut and extendability of matchings in distance-regular graphs
• Completely Disconnecting the Complete Graph

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)