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

作者：刘爱霞; 原军

来源：应用数学学报, 2013, (02): 209-216.

• 二部图
• 边连通度
• 限制边连通度 bipartite graphs
• connectivity
• restricted edge connectivity

设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)...

• 单位
  太原科技大学