Sufficient conditions for bipartite graphs to be super-k-restricted edge connected

AbstractFor a connected graph G=(V,E), an edge set S⊂E is a k-restricted edge cut if G−S is disconnected and every component of G−S contains at least k vertices. The k-restricted edge connectivity of G, denoted by λk(G), is defined as the cardinality of a minimum k-restricted edge cut. For U1,U2⊂V(G), denote the set of edges of G with one end in U1 and the other in U2 by [U1,U2]. Define ξk(G)=min{|[U,V(G)∖U]|:U⊂V(G),|U|=k≥1 and the subgraph induced by U is connected}. A graph G is λk-optimal if λk(G)=ξk(G). Furthermore, if every minimum k-restricted edge cut is a set of edges incident to a certain connected subgraph of order k, then G is said to be super-k-restricted edge connected or super-λk for simplicity. Let k be a positive integer and let G be a bipartite graph of order n≥4 with the bipartition (X,Y). In this paper, we prove that: (a) If G has a matching that saturates every vertex in X or every vertex in Y and |N(u)∩N(v)|≥2 for any u,v∈X and any u,v∈Y, then G is λ2-optimal; (b) If G has a matching that saturates every vertex in X or every vertex in Y and |N(u)∩N(v)|≥3 for any u,v∈X and any u,v∈Y, then G is super-λ2; (c) If the minimum degree δ(G)≥n+2k4, then G is λk-optimal; (d) If the minimum degree δ(G)≥n+2k+34, then G is super-λk