Disconnecting strongly regular graphs

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.

Cited by in corpus (3)

• Max-cut and extendability of matchings in distance-regular graphs
• Cometric Association Schemes
• Recent progress on graphs with fixed smallest eigenvalue