\input zb-basic
\input zb-ioport
\iteman{io-port 05644078}
\itemau{Yuan, Jun; Liu, Aixia; Wang, Shiying}
\itemti{Sufficient conditions for bipartite graphs to be super-$k$-restricted edge connected.}
\itemso{Discrete Math. 309, No. 9, 2886-2896 (2009).}
\itemab
Summary: For a connected graph $G=(V,E)$, an edge set $S \subset 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 $\lambda_k(G)$, is defined as the cardinality of a minimum $k$-restricted edge cut. For $U_1,U_2 \subset V(G)$, denote the set of edges of $G$ with one end in $U_1$ and the other in $U_2$ by $[U_1,U_2]$. Define $\xi_k(G) = \min\{\vert [U,V(G) \setminus U] \vert :U \subset V(G)$, $\vert U\vert = k \ge 1$ and the subgraph induced by $U$ is connected$\}$. A graph $G$ is $\lambda_k$-optimal if $\lambda_k(G) = \xi_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-$\lambda_k$ for simplicity. Let $k$ be a positive integer and let $G$ be a bipartite graph of order $n\ge 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)\cap N(v)|\ge 2$ for any $u,v\in X$ and any $u,v\in Y$, then $G$ is $\lambda_2$-optimal; (b) If $G$ has a matching that saturates every vertex in $X$ or every vertex in $Y$ and $|N(u)\cap N(v)|\ge 3$ for any $u,v\in X$ and any $u,v\in Y$, then $G$ is super-$\lambda_2$; (c) If the minimum degree $\delta(G)\ge \frac{n+2k}{4}$, then $G$ is $\lambda_k$-optimal; (d) If the minimum degree $\delta(G)\ge \frac{n+2k+3}{4}$, then $G$ is super-$\lambda_k$.
\itemrv{~}
\itemcc{}
\itemut{restricted edge connectivity; $k$-restricted edge connectivity; super-$\lambda {^{\prime}}$ graph; $\lambda _k$-optimal graph; super-$\lambda _k$ graph}
\itemli{doi:10.1016/j.disc.2008.07.022}
\end