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

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

图是超级-λ′的充分条件

设G=(V,E)是有限简单无向图.如果G的每个最小限制边割都孤立出一条边,则称G是超级-λ′的.笔者在一定意义上改进了文献[7]给出的图为超级-λ′的一个充分条件.     

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

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

直径为2的图是超级-λ′的充分条件

如果图G的每个最小限制边割都孤立出一条边,则称G是超级-λ′的．本文给出了直径为2的图是超级-λ′的一个充分条件．     

图是超级-λ′的度条件

笔者利用顶点的度给出了图是超级-λ′的两个充分条件,而且给出例子说明其最好可能性和独立性,这些结果在网络可靠性分析中有一定应用.     

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

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不是G*k图,则G是λk-最优的.     

图是λ4-最优及超级-λ3的最小度条件

为精确估计网络的可靠度,我们需要最优化其图模型的限制边连通度,证明一个n≥11阶最小度δ(G)≥[n/2]-3的λ4-连通图G,在一定的条件下是λ4-最优的.进而,若n≥12,则G是超级-λ3图.并举例说明了最小度的下界是最好可能的.     

图是超级-λ3的邻域条件

设G是有限简单无向图, k是正整数,使G-S的每个分支都包含至少k个点的边割S称为G的k-限制边割。若任意最小k-限制边割都孤立一个k阶连通子图,则称图G是超级-λk 的。本文应用邻域条件给出了图是超级-λ3 的充分条件。     

图的λ3最优性的充分条件

设G=(V,E)是有限简单无向图,U是一个边割.若G-U的每个分支的阶至少是3,则称U为G的3阶限制边割.G的3阶限制边连通度λ3(G)是G的3阶限制边割之中最少的边数.设F是图G的一个子图,令a(F)表示恰好有一个点在F上的边的数目,定义ζ3(G)=min{a(F):F是G的3阶连通导出子图}.如果λ3(G)=ζ3(G),则称G是λ3最优的.本文给出了图的λ3最优性的一个充分条件.     

超级λ_3-最优二部图的充分条件

图的k-限制边连通度是图的边连通度概念的推广,用它可以更加精确的度量网络的可靠性。通过讨论λ3-最优但非超级λ3-最优二部图的性质得到了二部图超级λ3-最优的充分条件。     

二部图λ3最优性的充分条件

本文给出了二部图λ3最优性的一些充分条件,它们在网络可靠性分析中有一定应用.     

图是超级限制性边连通的一个Ore型充分条件

设G是n阶简单无向图,G的顶点x的度记为d(x)。证明了如果对G中每一对不相邻的顶点x和y都有d(x) d(y)≥n＋2,那么,G是超级限制性边连通的,除非n≥6是偶数且G＝2Kn/2∪F2,这里F2是G的一个2因子,这一结果是对图的极大限制性边连通性的Ore型充分条件的进一步扩展。     

图是λ5-最优的充分条件

文章给出了图是λ5-最优的邻域交条件.设G是一个λ5-连通图,定义ξ5（G）=min{｜[X,]｜：X∈V（G）,｜X｜=5,G[X]连通},若λ5（G）=ξ3（G）,则称G是λ5-最优的.若对G中任意一对不相邻的顶点u和v,都有｜N（u）∩N（v）｜≥5且G满足ξ3（G）≤V（G）/2＋10,｜V（G）｜≥31,则...     

λ_4-最优图的一个充分条件

文章给出了λ4-最优图的一个充分条件.设G是阶为n≥11的λ4-连通图,若对G中任意一对不相邻顶点u,v,有｜N（u）∩N（v）｜≥6且G｜N（u）∩N（v）｜至少包含16条边,则G是λ4-最优的.     

图是λ′最优和超级λ′的充分条件

设G是有限简单无向图,使G-S的每个分支都不含孤立的边割S称为G的限制边割.G的限制连连通度λ′(G)是G的限制边割之中最少的边数,定义ξ(G)=min{d(x)+d(y)-2;xy∈E(G)}为G的最小边度.如果λ′(G)=ξ(G),则称G是λ′最优的.若任意最小限制边割都弧立一边,则称图G是超级λ′的.应用范型度条件给出了图是λ′最优和超级λ′的令分条件.     

图是极大限制边连通的一个充分条件

设G是n阶简单无向连通图,G的限制边割是删除它以后G不连通,且留下的每个分支不含孤立点的边子集;限制边割的最小基数称为限制边连通度.记G的顶点x的度为d(x)。证明了若对超级连通图G中任意一对不相邻的顶点x和y都有d(x) (dy)n,则G是极大限制边边通的当且仅当G不同构一种特殊图G。     

λ5-最优图的一个充分条件

设G是一个λ5-连通图,定义ξ5(G)=min{|[X,X]|:X■V(G),|X|=5,G[X]是连通子图},若λ5(G)=ξ5(G),则称G是λ5-最优图.文章给出了满足顶点数v≥17且最小度δ≥v/2-4的λ5-连通图G在一定特殊条件下是λ5-最优图的一个充分条件.     

k—连通图为Dλ—连通的一个充分条件

本文在对有限简单图给出 D_λ—连通的定义之后,证明了下述定理:设 G 是n 阶 k—连通(k≥3)的有限简单图,如果对任意的 Y∈I_k(G,λ),有sum from i=1 to k (k+i-2)/(k-1)s_i(Y、λ)>n-k(λ-1),则 G 是 D_λ—连通的.     

二部图λ4-最优性和超级性的范型条件

作者给出了二部图是λ4-最优的和超级-λ4的范型条件,而且给出例子说明其独立性.这些结果在网络可靠性分析中有一定应用.