图的λ_4最优性和超级性的度条件

设G是有限简单无向图,使G-S每个分支的阶至少为4的边割S称为G的4阶限制边割.G的4阶限制边连通度λ4(G)是G的4阶限制边割之中最少的边数,达到最小的叫λ4边割.定义ξ4(G)=min{(U):UV(G),G[U]是4阶连通子图},此处(U)表示恰好有一个端点在U中的边数.若λ4(G)=ξ4(G),则称G是λ4最优的.若任意λ4边割都孤立一个4阶连通子图,则称G是超级λ4连通的.给出图是λ4最优和超级λ4连通的度条件,并举例说明条件的最好可能性.     

图是λ3-最优和超级-λ3的范型条件

设G是有限简单无向图,使G-S的每个分支都包含至少k个点的边割S称为G的k-限制边割。G的k-限制边连通度λk(G)是G的k-限制边割之中最少的边数。定义ξk(G)=min{[U,U-]:U V(G),|U|=k,G[U]是连通的},若λk(G)=ξk(G),则称G是λk-最优的。若任意最小k-限制边割都孤立一个k阶分支,则称图G是超级-λk的。应用范型条件给出了图是λ3-最优和超级-λ3的充分条件。     

二部图λ_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最优性的一个原子条件.     

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-最优的.     

图是λ_k-最优的和超级-λ_k的度条件

设S是连通图G中的一个边子集。若G-S不连通且它的每个连通分支的阶至少为k,则称S是G的一个k限制边割。图G的最小k限制边割的边数称为G的k限制边连通度,记为λk(G).义ζk(G)=min{|[X,X]|∶|X|=k,G[X]连通},其中X=V(G)\X.若λk(G)=ζk(G),则称G是λk-最优的。如果图G的每个最小k限制边割都孤立了一个k阶连通子图,那么称G是超级-λk的。设k是一个不小于2的正整数且G是一个阶不小于2庇的图。本文证明了若对于G中任意一对不相邻顶点u,v都有d(u)+d(v)≥ν+2k-4且G不属于一类特殊图,则G是λk-最优的。最后,给出了图是超级-λk的一个充分条件。     

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

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

超级-λ'无三角图的度和充分条件

设S是连通图G的一个边割。若G-S不包含孤立点,则称S是G的一个限制边割。如果图G的每个最小限制边割恰好分离出图G的一条边,则称图G是超级限制边连通的,简称超级-λ'的。设G是一个阶n≥4的连通无三角图。本文证明了若G中任意满足dist(u,v)=2的点对u,v∈V(G)有d(u)+d(v)≥2[n+2/4]+3,则G是超级-λ'的。最后,举例说明该结论是最好的。     

图是极大3限制边联通的充分条件

设S是连通图G中的一个边子集。若G S不连通且它的每个连通分支的阶至少为k,则称S是G的一个k限制边割。图G的最小k限制边割的边数称为G的k限制边连通度,记为λκ(G)。定义ξκ(G)=min{|［X,X］|:|X|=k,G［X］连通},其中X=V(G)＼X。若λk (G)=ξk(G),则称G是极大k限制边连通的。设G是一个围长至少为5的λ3 连通图。本文证明了若G中不存在5个点u1,u2,v1,v2,v3使得d(ui,vj)≥3(i=1,2;j=1,2,3),则G是极大3限制边连通的。     

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

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

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

设G=(V,E)足有限简单无向图,U,是一个边割.若G-U的每个分支的阶至少是4,则称U为G的4阶限制边割.G的4阶限制边连通度λ4(G)是C的4阶限制边割之中最少的边数.对图G的一个子图F,令a(F)表示恰好有一个点在F上的边的数日,定义ξ4(G)=min{a(F):F是G的连通的导出子图,|F|=4}为F的4阶最小边度,用D,g,δ 分别表示G的直径,围长和最小度.本文证明了:如果|G|≥11,D≤g-6且δ≥3,那么λ4(G)=ξ4(G).