The k-Restricted Edge Connectivity of Balanced Bipartite Graphs

Abstract

For a connected graph G = (V, E), an edge set ${S\subset E}$ is called 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 two disjoint vertex sets ${U_1,U_2\subset V(G)}$, denote the set of edges of G with one end in U ₁ and the other in U ₂ by [U ₁, U ₂]. Define ${\xi_k(G)=\min\{|[U,V(G){\setminus} U]|: U}$ is a vertex subset of order k of G and the subgraph induced by U is connected}. A graph G is said to be λ _k -optimal if λ _k (G) = ξ _k (G). A graph is said to be super-λ _k if every minimum k-restricted edge cut is a set of edges incident to a certain connected subgraph of order k. In this paper, we present some degree-sum conditions for balanced bipartite graphs to be λ _k -optimal or super-λ _k . Moreover, we demonstrate that our results are best possible.