超级限制边连通二部图的充分条件

Sufficient Conditions for Bipartite Graphs to be Super Restricted Edge-connected

设S是连通图G的一个边割.若G-S不包含孤立点,则称S是G的一个限制边割.图G的最小限制边割的边数称为G的限制边连通度,记为λ′(G).如果图G的限制边连通度等于其最小边度,则称图G是最优限制边连通的,简称λ′-最优的.进一步,如果图G的每个最小限制边割恰好分离出图G的一条边,则称图G是超级限制边连通的,简称超级-λ′的.设G是一个最小度δ(G)≥2的n≥4阶二部图,ξ(G)是G的最小边度.本文证明了(a)若ξ(G)≥(n/2-2)(1+1/(δ(G)-1)),则G是λ′-最优的;(b)若ξ(G)>((n/2)-2)(1+1/(δ(G)-1)),则G是超级-λ′的,除非图G是K_(2,n-2),n≥6或是Cartesian积图K_(n/4,n/4)×K_2,其中n≥8且n整除4.最后,论文举例说明该结果是最好可能的.

An edge cut S of a connected graph G is called a restricted edge cut if G-S contains no isolated vertices. The minimum caxdinality of all restricted edge cuts is called the restricted edge connectivity λ′（G） of G. A graph G is optimally restricted edge-connected, for short λ′-optimal, if λ′（G）=ξ（G）, where ξ（G） is the minimum edge degree of G. A graph is said to be super restricted edge-connected, for short super-λ′, if every minimum restricted edge cut isolates an edge. Let G be a connected bipartite graph of order n, minimum degree δ（G）≥2 and minimum edge degree ξ（G）. In this paper, we prove that： （a） If ξ（G）≥（n/2-2）（1＋1/δ（G）-1）, then G is λ′-optimal; （b） If ξ（G）〉（n/2-2）（1＋1/δ（G）-1）, then G is super-λ′ with the exception of the complete bipartite graph K2,n-2,n≥6, and the Cartesian product graph Kn/2 ,n/4×K2 with n≥8 and n is divisible by 4. Moreover, we demonstrate that these results are best possible.