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