二部图λ_k(k=3,4)最优性的充分条件

Sufficient Condition for the λ_k-Optimality(k=3,4) of Bipartite Graphs

为精确估计网络的可靠度,需要最优化其图模型的限制边连通度。证明了:1,如果G是连通二部图,且δ(G)≥3,对于满足d(x,y)=2的任意两点x,y,有d(x)+d(y)≥2[n(G)/4]+4,则G是λ3-最优的。2,若G是λ4-连通图,且|G|≥11,δ(G)≥4,对于满足d(x,y)=2的任意两点x,y,有d(x)+d(y)≥2[n(G)/4]+6,则G是λ-最优的。

In order to estimate the security of a network more accurately,the restricted edge connectivity of the graph model is need optimized. It is proved：1, Let G be a connected bipartite graph and δ（G）≥3.If d（x）＋d（x）＋d（y）≥2[n（G）/4]＋for each pair x,y in V（G） such that d（x,y） =2 then G is λ3-optimal.2, Let G be a λ4-connected bipartite graph with n（G）≥ 11 ,and δ（G） ≥3. If for each pair x ,y ∈ V（G） such that d（x ,y） = 2 ,then G is λ4-optimal.