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

为精确估计网络的可靠度,需要最优化其图模型的限制边连通度.证明了: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是λ4-最优的.     

三阶边连通度最优性的一个充分条件

设G是有限简单无向图,D,g,δ分别表示G的直径、围长和最小度.设U是连通图G的边子集.如果G-U不连通,且每个连通分支至少有3个点,则称U是G的一个三阶限制边割,|U|的最小值称为G的三阶限制边连通度,记为λ3(G).一个三阶连通子图的最小外度定义为ζ3(G)=min{|(X,(X))|:X∈V(G),|X|=3,G[X]连通}.证明如果D≤g-4且δ≥3,那么λ3(G)=ζ3(G).