1 Introduction

All graphs considered are finite, undirected and simple in this paper. Let G be a graph. The vertex set and the edge set of G are denoted by V(G) and E(G) respectively. Let B be a subset of the vertex set V(G) of G. The graph G[B] is induced by B, which is always denoted by B for convenience without ambiguity. Also, E(B) denotes the set of edges in B. The graph \(G-B\) is obtained from G by deleting the vertices (and edge incident to them) of B. If \(B=\left\{ u\right\} \), we denote \(G-B\) by \(G-u\) for convenience. Let E be a subset of the edge set E(G) of G. The graph \(G-E\) is defined with vertex set \(V(G-E)=V(G)\) and edge set \(E(G)-E\). Let S and T be two disjoint subsets of V(G) (or two vertex-disjoint subgraphs of G). Define E(S, T) to be the set of edges of which one end vertex is in S and the other end vertex is in T. If G contains a cycle, the girth of G is the length of a shortest cycle in G. If G is a forest, its girth is defined to be \(\infty \). Let G be a connected graph. A subset S of V(G) is said to be a (vertex) cut set, if \(G-S\) is not connected or a singleton vertex. A subset N of the edge set E(G) of G is said to be an edge cut set, if there exist two disjoint subsets A and B of V(G) such that \(V(G)=A\bigcup B\) and \(E(A,B)=N\). A subset N of E(G) is said to be a cyclic edge cut set, if N is an edge cut set and \(G-N\) has at least two components which contain a cycle. The (cyclic) edge (vertex)-connectivity of a graph is the minimum size of a (cyclic) edge (vertex) cut set of G.

Let G be a cubic graph of cyclic edge-connectivity at least \(\ell \ge 4\). Suppose \(e=uv\) is an edge. The reduction of the edge e is an operation on G by deleting the two vertices u and v, connecting the two neighbours \(u_{1}\) and \(u_{2}\) of u, and also connecting the two neighbours \(v_{1}\) and \(v_{2}\) of v. The formed graph is still a simple cubic graph, since G has cyclic edge-connectivity at least \(\ell \ge 4\) and thus G contains no triangle. For more studies of edge-reductions in a cubic graph with cyclic edge-connectivity at least \(\ell \ge 4\), one may refer to [13].

Let G be a k-regular graph which is not the complete graph \(K_{k+1}\). The graph G is called a strongly regular graph, if there exist two integers \(\lambda \) and \(\mu \), such that the number of the common neighbours of any two adjacent vertices in G is equal to \(\lambda \) and the number of the common neighbours of any two distinct non-adjacent vertices in G is equal to \(\mu \). In [6], it proved that each connected strongly regular graph G of degree \(k\ge 3\) has (vertex-)connectivity k. Moreover, each (vertex) cut set of size k is precisely the set of neighbours of a vertex in G. Also, the minimum number of vertices of a set disconnecting a connected strongly regular graph into non-singleton components was studied in [7] and [8]. There is a link [2] where many of the known strongly regular graphs were listed. The connectivity of distance-regular graphs, of which the concept is a generalization of strongly regular graphs, was studied in [4] and [5].

In this paper, for any connected strongly regular graph G of degree \(k\ge 3\), we show that if G is not \(K_{3,3}\), then its cyclic edge-connectivity is \((k-2)c\), where c is the girth of G and thus \(c=3,4\) or 5. Moreover, if G is not the triangular graph srg-(10, 6, 3, 4), the complete multi-partite graph \(K_{2,2,2,2}\) or the lattice graph srg-(16, 6, 2, 2), then each cyclic edge cut set of size \((k-2)c\) is precisely the set of edges incident with a cycle of length c in G. The Proofs in this paper are mainly based on spectrum technique [3, 12]. For any terminology used but not defined here, one may refer to [1].

2 Main Tools

Let G be a graph whose vertices are denoted by \(1,2,\ldots ,v\), respectively. The adjacency matrix of G is a square matrix \(A=(a_{ij})\) indexed by the vertices of G such that \(a_{ij}=1\) if the vertex i is adjacent to the vertex j in G and \(a_{ij}=0\) otherwise. The eigenvalues of G are the eigenvalues of its adjacency matrix. Strongly regular graphs were studied extensively based on spectrum technique.

In this paper, we always denote a connected strongly regular graph G of degree k by srg-\((v,k,\lambda ,\mu )\), where \(v=|V(G)|\), \(\lambda \) is the number of common neighbours of any two adjacent vertices of G, and \(\mu \) is the number of common neighbours of any two distinct non-adjacent vertices of G, respectively. It is easy to see that the the girth c of G is equal to 3 (\(\lambda >0\)), 4 (\(\lambda =0,\mu >1\)) or 5 (\(\lambda =0, \mu =1\)). If \(k=2\), then G is a 4-cycle or a 5-cycle (trivial case). Through this paper, we always suppose \(k\ge 3\). Denote the eigenvalues with multiplicities of G by \(k^{1},~r^{f}\) and \(s^{g}\), where \(r\ge 0>s\) and 1, f, g are the multiplicities of eigenvalues k, r, s, respectively (The multiplicity of k is 1 by Perron-Frobinius Theorem). For more fundamental properties of strongly regular graphs, one may refer to Chapter 10 in [11].

The eigenvalue interlacing methods were used in [12]. It is a useful tool to study the structure of graphs, especially for strongly regular graphs. To prove the main result, we first introduce some fundamental results in the certain form as we consider only strongly regular graphs in this paper.

By Sections 10.1 and 10.2 in [11], we have the following conclusion.

Lemma 2.1

Let G be a strongly regular graph srg-\((v,k,\lambda ,\mu )\). Then \(k(k-\lambda -1)=(v-k-1)\mu \) and \(r=\frac{\lambda -\mu +\sqrt{(\lambda -\mu )^{2}+ 4(k-\mu )}}{2},s=\frac{\lambda -\mu -\sqrt{(\lambda -\mu )^{2}+ 4(k-\mu )}}{2}\).

By Corollary 4.8.4 in [3] or Theorem 3.5 in [12], we have the following conclusion in certain form (The second smallest laplace eigenvalue \(\mu _{2}\) of G is equal to \(k-r\)).

Lemma 2.2

Let G be a strongly regular graph srg-\((v,k,\lambda ,\mu )\). For any subset \(S\subseteq V(G)\), we have \(|E(S,\overline{S})|\ge \frac{(k-r)|S|(v-|\overline{S}|)}{v}\), where \(\overline{S}=V(G)-S\).

The following conclusion is on Seidel’s classification [15] of connected strongly regular graphs with minimum eigenvalue \(s =-2\).

Theorem 2.3

(Seidel [15]) Let G be a strongly regular graph srg-\((v,k,\lambda ,\mu )\) with \(s =-2\). Then G is precisely one of the following graphs:

  1. 1.

    the complement of the ladder graph \((v,k,\lambda ,\mu )=(2n, 2n-2, 2n-4, 2n-2), r=0\),

  2. 2.

    a lattice graph, \((v,k,\lambda ,\mu ) = (n^{2}, 2(n -1), n -2, 2), r= n-2\),

  3. 3.

    the Shrikhande graph, \((v,k,\lambda ,\mu ) = (16, 6, 2, 2), r=2\),

  4. 4.

    a triangular graph, \((v,k,\lambda ,\mu ) = ((^{n}_{2}), 2(n - 2), n - 2,4), r = n-4\),

  5. 5.

    three Chang graphs, \((v,k,\lambda ,\mu ) = (28,12,6,4), r=4\),

  6. 6.

    the Petersen graph, \((v,k,\lambda ,\mu ) = (10, 3, 0,1), r=1\),

  7. 7.

    the Clebsch graph, \((v,k,\lambda ,\mu ) = (16,10,6,6), r=2\),

  8. 8.

    the Schl\(\ddot{a}\)fli graph, \((v,k,\lambda ,\mu ) = (27,16,10,8,), r=4\).

The (vertex-)connectivity of strongly regular graphs was studied in [6]. The proof is based on Theorem 2.3 and eigenvalue interlacing technique.

Theorem 2.4

( [6]) Let G be a connected strongly regular graph of degree \(k\ge 3\). Then its connectivity is equal to k. Moreover, each (vertex) cut set of size k is the set of all neighbours of a vertex of G.

There are further restrictions on the parameters and more characterizations of strongly regular graphs in [10, 14].

3 Main Results

Based on the conclusions displayed in Section 2, the minimum size of a (vertex) cut set disconnecting connected strongly regular graphs into non-singleton components was studied in [7] and [8]. Using an additional tool, Tutte Theorem [16], the extendability of matchings of strongly regular graphs was studied in [9]. There are already some results of edge cut sets of strongly regular graphs in [8, 9]. We can not quote directly and we need a more refined discussion to prove the main result.

We will prove the main result in three cases \(c=3 (\lambda>0), 4 (\lambda =0, \mu >1)\) and \(5 (\lambda =0, \mu =1)\), respectively, where c is the girth of G. Notice that we can search from the table [2] when we consider small strongly regular graphs.

Theorem 3.1

Let G be a connected strongly regular graph srg-\((v,k,\lambda ,\mu )\) with \(k\ge 3\) and \(\lambda >0\). The cyclic edge-connectivity of G is \(3k-6\). Moreover, if G is not the triangular graph srg-(10, 6, 3, 4), \(K_{2,2,2,2}\) (the complement of a ladder graph) or the lattice graph srg-(16, 6, 2, 2), then each cyclic edge cut set of size \(3k-6\) is precisely the set of edges incident with a triangle in G.

Proof

The graph G contains a triangle as \(\lambda >0\). Each set of edges incident with a triangle is obviously a cyclic edge cut set of size \(3k-6\) in G. Let M be a cyclic edge cut set of G with minimum size (if exists) such that there are no triangle components in the graph \(G-M\). By the choice of M, there are only two components, say A and B, such that \(V(G)=A\bigcup B\) and \(M=E(A,B)\). We can suppose \(4\le |A|\le \frac{v}{2}\) without loss of generality, since each of A and B contains a cycle and is not a triangle. In the following, we will prove that \(|E(A,B)|\ge 3k-6\). Moreover, if G is not the triangular graph srg-(10, 6, 3, 4), \(K_{2,2,2,2}\) or the lattice graph srg-(16, 6, 2, 2), then \(|E(A,B)|\ge 3k-5\). It suffices to prove the conclusion. Notice that each of the three graphs contains a 4-clique and the set of edges incident with a 4-clique is a cyclic edge cut of size \(3k-6=18-6=12\).

Using the table [2], we obtain \(k\ne 3\), since there is no cubic strongly regular graph with a triangle. If \(k=4\), then G is \(K_{2,2,2}\) or the Lattice graph srg-(9, 4, 1, 2). For \(K_{2,2,2}\) the conclusion is trivial. For the Lattice graph srg-(9, 4, 1, 2), we have \(|A|=4\) and thus \(|E(A,B)|\ge 4k-8=8\ge 3k-5=7\) as there are at most 4 edges inside A. Also, we have \(k\ne 5\), since there is no 5-regular strongly regular graph with a triangle. In the following discussions, we can assume \(k\ge 6\).

If \(4\le |A|\le k-2\), then \(|E(A,B)|\ge |A|(k+1-|A|)\ge 3k-6\). The two inequalities are equalities simultaneously if and only if A is a clique of size \(k-2\). In fact, the first equality implies A is a clique. If A is a clique of size at most \(k-3\), which implies \(k\ge 7\), then \(|E(A,B)|=|A|(k+1-|A|)\ge 4(k-3)>3k-6\), a contradiction. Now suppose that A is a clique of size \(k-2\). Therefore, we have \(\lambda \ge k-4\). Denote the subset of B in which each vertex has a neighbour in A by N. By Theorem 2.4, we have \(|N|\ge k-2\) as \(|B|\ge |A|=k-2\). For any vertex u in N, there are at least \(\lambda -1\ge k-5\) neighbours in A, which implies \((k-2)(k-5)\le |E(A,B)|=3k-6\) and thus \(k\le 8\). If \(k=8\), the equality is satisfied, and then we have \(|B|=k-2\) and \(\lambda =k-4\). Thus, G is the graph srg-(12, 8, 4, 8). It is easy to see that the graph srg-(12, 8, 4, 8) has no clique of size \(k-2=6\), a contradiction. Using the table [2], we obtain \(k\ne 7\), since there is no connected 7-regular strongly regular graph with a triangle. If \(k=6\), then G has a clique of size 4 and \(\lambda \ge 2\). Without regard to the three graphs, the triangular graph srg-(10, 6, 3, 4), \(K_{2,2,2,2}\) and the lattice graph srg-(16, 6, 2, 2), from the table [2] there are only two graphs, srg-(13, 6, 2, 3) (unique with these parameters) and the Shrikhande graph srg-(16, 6, 2, 2) left. As we know, the Shrikhande graph contains no 4-clique. Also, it is easy to check that the graph srg-(13, 6, 2, 3) contains no 4-clique, a contradiction.

Now consider the case \(|A|=k-1\). If each vertex of A has at least 3 neighbours in B, then \(|E(A,B)|\ge 3(k-1)\ge 3k-5\), as required. Suppose there is a vertex u of A such that u has precisely two neighbors in B, which are denoted by x and y respectively. Set \(N=\left\{ x,y\right\} \). We have \(|E(A,N)|\ge 2\lambda \) and \(|E(A,B-N)|= (k-2)(k-\lambda -1)\) as each vertex in \(A-u\) has precisely \(k-\lambda -1\) neighbours in \(B-N\). It implies \(|E(A,B)|\ge 2\lambda +(k -2)(k-\lambda -1)=(k-1)(k-2)-(k-4)\lambda \ge 3k-6\) as G is not complete graph and thus \(\lambda \le k-2\). If the two inequalities are equalities simultaneously, then we have \(\lambda =k-2\). By Lemma 2.1 we have \(k(k-\lambda -1)=(v-k-1)\mu \) and thus \(\mu \le 2\) as \(v\ge 2|A|=2k-2\). If \(\mu =2\), then \(k=6\) and thus G is with parameters (10, 6, 4, 2), which is impossible as there is no strongly regular graph with these parameters from the table [2]. If \(\mu =1\), then G is with parameters \((2k+1,k,k-2,1)\). It is easy to see that G is not a conference graph which is the form srg-\((4t+1,2t,t-1,t)\). Thus the eigenvalues of G are all integers. In particular, by Lemma 2.1 we have that \((\lambda -\mu )^{2}+4(k-\mu )=(k-1)^{2}+4\) is the square of an integer, which is impossible.

It remains the only case \(6\le k\le |A|\le \frac{v}{2}\). By Lemma 2.2, we have \(|E(A,B)|\ge \frac{(k-r)|A||B|}{v}\). If G is a conference graph srg-\((4t+1,2t,t-1,t)\), then we have \(k-r=\frac{4t+1-\sqrt{4t+1}}{2}\ge 6\) for \(t\ge 4\) and thus \(|E(A,B)|\ge \frac{k(k-r)}{2} \ge 3k\). If \(t=3\), then G is srg-(13, 6, 2, 3) and thus \(|E(A,B)|\ge 13\) as \(|A|=6\) and \(k-r=\frac{13-\sqrt{13}}{2}\). Now suppose G is not a conference graph and thus all the eigenvalues are integers. If \(k-r\ge 6\), then we have \(|E(A,B)|\ge \frac{k(k-r)}{2} \ge 3k\). We can assume \(r\ge k-5\). If \(s=-2\), noticing \(r\ge k-5\) and \(6\le k\le |A|\le \frac{v}{2}\), by Theorem 2.3 we need only to consider the lattice graph srg-(16, 6, 2, 2), the Shrikhande graph srg-(16, 6, 2, 2) and the lattice graph srg-(25, 8, 3, 2). For the two graphs with parameters (16, 6, 2, 2), we have \(r=2\) and thus \(|E(A,B)|\ge \frac{(k-r)|A||B|}{v}\ge 15\) for \(6\le |A|\le 8\). For the lattice graph srg-(25, 8, 3, 2), we have \(r=3\) and thus \(|E(A,B)|\ge \frac{(k-r)|A||B|}{v}\ge 27\) as \(8\le |A|\le 12\). If \(s\le -3\), we have \(k-1\ge k-\mu =-rs\ge 3k-15\), which implies \(k\le 7\). Since there is no 7-regular connected strongly regular graph with a triangle, we have \(k=6\) and then G is srg-(15, 6, 1, 3) with \(r=1\) from the table [2]. It implies \(|E(A,B)|\ge \frac{(k-r)|A||B|}{v}\ge 18\) as \(6\le |A|\le 7\). We complete the proof. \(\square \)

Let G be a connected strongly regular graph srg-\((v,k,\lambda ,\mu )\) with \(k\ge 8\) and \(\lambda >0\). From the proof of Theorem 3.1, we have \(|E(A,V(G)-A)|\ge 3k\) for any subset A with \(k\le |A|\le v-k\).

Theorem 3.2

Let G be a connected strongly regular graph srg-\((v,k,\lambda ,\mu )\) with \(k\ge 3\), \(\lambda =0\) and \(\mu \ge 2\). If G is not \(K_{3,3}\), then the cyclic edge-connectivity of G is \(4k-8\). Moreover, each cyclic edge cut set of size \(4k-8\) is precisely the set of edges incident with a 4-cycle in G.

Proof

By hypothesis, we have \(k\ge 4\) and we can suppose \(k\ge 5\) as the conclusion is trivial for \(K_{4,4}\). Since the girth of G is 4, it is easy to see that each set of edges incident with a 4-cycle in G is a cyclic edge cut set of size \(4k-8\). Let M be a cyclic edge cut set of minimum size (if exists) such that none of the components of \(G-M\) is a 4-cycle. By the choice of M, there are two components, say A and B, such that \(V(G)=A\bigcup B\) and \(M=E(A,B)\). Without loss of generality, we can suppose \(5\le |A|\le \frac{v}{2}\) as each of A and B contains a cycle and is not a 4-cycle. We will prove that \(|E(A,B)|\ge 4k-7\) in the following.

Assume that \(5\le |A|\le 2k-4\). By \(Tur\acute{a}n^{,}s\) Theorem ( [1] Theorem 7.9), we have \(|E(A,B)|\ge k|A|-\frac{|A|^{2}}{2}\ge 4k-8\) as there is no triangle in G and also in A. The equality is satisfied if and only if the induced graph by A is a regular complete bipartite graph of size \(2k-4\). Suppose the equality is satisfied. Thus \(v\ge 4k-8\) and \(\mu \ge k-2\). By \(k(k-1)=(v-k-1)\mu \) in Lemma 2.1, we have \(\mu =k, v=2k\) or \(\mu =k-1, v=2k+1\), which is contradict to \(v\ge 4k-8, k\ge 5\).

Now we consider the remained case \(2k-3\le |A|\le \frac{v}{2}\). Since G is not a conference graph, the eigenvalues of G are all integers. By Theorem 2.3 we have \(s\le -3\) for \(k\ge 5\). By \(r(-s)=k-\mu \le k-2\), we have \(r\le \frac{k-2}{3}\) and thus \(k-r\ge \frac{2k+2}{3}\). By Lemma 2.2, we have \(|E(A,B)|\ge \frac{(k-r)|A||B|}{v}\ge \frac{(k+1)(2k-3)}{3}\ge 4k-7\). We complete the proof. \(\square \)

Theorem 3.3

Let G be a connected strongly regular graph srg-\((v,k,\lambda ,\mu )\) with \(k\ge 3\), \(\lambda =0\) and \(\mu =1\). The cyclic edge-connectivity of G is \(5k-10\). Moreover, each cyclic edge cut set of size \(5k-10\) is precisely the set of edges incident with a 5-cycle in G.

Proof

By Theorem 9.1.5 in [3], G is one of the Petersen graph srg-(10, 3, 0, 1), the Hoffman singleton graph srg-(50, 7, 0, 1) and srg-(3250, 57, 0, 1) (the existence of the graph with the last group of parameters is unknown). For these graphs, each set of edges incident with a 5-cycle is indeed a cyclic edge cut set of size \(5k-10\). For the Petersen graph, the conclusion is trivial as \(v=10\). For the latter two graphs, similar to the previous proof, we need only to prove that \(|E(A,B)|\ge 5k-9\) for any subset \(6\le |A|\le \frac{v}{2}\), where \(B=V(G)-A\). By Lemma 2.2, we have \(|E(A,B)|\ge {}_{\phantom {0_0}} \frac{(k-r)|A||B|}{v}\). For the Hoffman singleton graph srg-(50, 7, 0, 1), we have \(r=2\) and thus \(|E({A,B})|\ge {}_{\phantom {0_0}} \frac{(7-2)\times 6\times (50-6)}{50}\ge 26\) as \(6\le |A|\le \frac{v}{2}\). For the group of parameters (3250, 57, 0, 1), we have \(r=7\) and thus \(|E({A,B})|\ge {}_{\phantom {0_0}}\frac{(57-7)\times 6\times (3250-6)}{3250}\ge 299\ge 276\) as \(6\le |A|\le {}_{\phantom {0_0}}\frac{v}{2}\). We complete the proof. \(\square \)