k阶限制边连通度最优的一个充分条件

设S是图G的一个边子集,若G-S不连通且每个分支的阶至少为k,则称S为G的一个k-限制边割。若G有k-限制连割,G的最小k-限制边割的边数称为G的k阶限制边连通度,记为λk(G).记ξk(G)=min{|[X,]|∶|X|=k,G|X|连通},若λk(G)=ξk(G),则称G是λK-最优的。证明了若对G中任意一对不相邻的顶点x,y都有d(x)+d(y)≥n+2(k-2),且G不是Gk*图,则G是λk-最优的。

图是超级λ_k-连通(k=4,5)的一个Ore型充分条件

图的k阶限制边连通度λk(G)对衡量网络可靠性起重要的作用.本文给出图是超级λk(k=4,5)连通的一个Ore型条件.

图的λ_k最优性和超级性的充分条件

分别给出了直径为2的图的λ3最优性和不含三角的图是超级λk的一个充分条件,讨论了不含三角的图的λk最优性和λk超级性的关系,这些结果在网络可靠性分析中有一定应用.

图的λ_k最优性和超级性(k=2,3)的邻域交与边度条件

本文给出了图的λk最优性和超级性(k=2,3)的用邻域交与边度表示的充分条件.

二部图λ_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是λ-最优的。

二部图λ_3最优性的一个原子条件

设G=(V,E)是有限简单无向图,U是G的一个边割,k是一正整数.若G-U的每个分支的阶至少为k,则称U为G的一个k阶限制边割.定义G的k阶限制边连通度λk(G)为G的k阶限制边割中最少的边数,达到最小的称为λk割.定义ξk(G)=min{(F):F是G的k阶连通子图},其中(F)表示恰好有一个端点在F上的边的数目.如果λk(G)=ξk(G),则称G是λk最优图.本文给出了二部图λ3最优性的一个原子条件.