共查询到20条相似文献,搜索用时 31 毫秒
1.
图是λ′最优和超级λ′的充分条件 总被引:1,自引:1,他引:0
设G是有限简单无向图,使G-S的每个分支都不含孤立的边割S称为G的限制边割.G的限制连连通度λ′(G)是G的限制边割之中最少的边数,定义ξ(G)=min{d(x)+d(y)-2;xy∈E(G)}为G的最小边度.如果λ′(G)=ξ(G),则称G是λ′最优的.若任意最小限制边割都弧立一边,则称图G是超级λ′的.应用范型度条件给出了图是λ′最优和超级λ′的令分条件. 相似文献
2.
设G=(V,E)是一个连通图.如果λ3(G)=ξ3(G),则G是λ3-最优或者极大3-限制性边连通的,其中ξ3(G)=min{|[X,Y]|:XV,|X|=3,G[X]连通}.G的逆度是指R(G)=∑v∈V1/d(v).本文主要研究R(G)与顶点数n,最小度δ及ξ3的关系,并由此得到一函数,用这一函数来限制R(G),使G是λ3-最优的. 相似文献
3.
4.
设G是有限简单无向图,k是正整数.使G-S每个分支的阶不小于k的边割S称为G的k阶限制边割.G的四阶限制边连通度λ4(G)是G的四阶限制边割之中最少的边数.若对于任意边e∈E(G),均有λ4(G-e)=λ4(G)-1,则称G是极小四阶限制边连通图.定义ξ4(G)=min {(e)(U):U(∪)V(G),G[U]是四阶连通导出子图},此处(e)(U)表示恰好有一个点在U上的边的数目.若λ4(G)=ξ4(G),则称G是λ4最优的.若每个5阶限制边割都孤立出G的一个5阶连通子图,则称G是超级5阶边连通的.笔者给出:极小四阶限制边连通图若不是λ4最优的,则是3正则,围长为5,任意边都关联5圈,且是超级5阶边连通的图. 相似文献
5.
李锐 《石河子大学学报(自然科学版)》2006,24(6):782-785
如果图G的每个极小点割(边割)都孤立一个点,则图G是超点连通(超边连通)的。图G的至少孤立一条边的边割称为限制性边割,其最小基数计作λ′(G)。当λ′(G)=ξ(G)时,称图G是λ′-最优,其中ξ(G)是图G的最小边度。本文给出了点积图是超点连通、超边连通、的一些充分条件。 相似文献
6.
设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-最优的. 相似文献
7.
设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的充分条件。 相似文献
8.
《山西大学学报(自然科学版)》2015,(1)
设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的一个充分条件。 相似文献
9.
如果G-F不连通且每个连通分支至少含有两个顶点,则连通图G的边子集F称为限制边割.如果图G的每个最小限制边割都孤立G中的一条边,则称G是超限制边连通的(简称超λ′).对于满足|F|≤m的任意子集FE(G),超λ′图G的边容错性ρ′(G)是使得G-F仍是超λ′的最大整数m.这里给出了min{k1+k2-1,υ1k2-2k1-2k2+1,υ2k1-2k1-2k2+1}≤ρ′(G1×G2)≤k1+k2-1,其中,对每个i∈{1,2},Gi是阶为υi的ki正则ki边连通图且ki≥4,G1×G2是G1和G2的笛卡尔乘积.并给出了使得ρ′(G1×G2)=k1+k2-1的一些充分条件. 相似文献
10.
11.
《太原科技大学学报》2015,(5)
设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是超级-λ'的。最后,举例说明该结论是最好的。 相似文献
12.
设S是连通图G的一个边割。若G-S不包含孤立点,则称S是G的一个限制边割。图G的最小限制边割的边数称为G的限制边连通度,记为λ'(G).如果图G的限制边连通度等于其最小度,则称图G是最优限制边连通的,简称λ'-最优的。设G是一个n阶的连通无三角图,且最小度δ(G)≥2.文章证明了,若最小边度ξ(G)≥(n/2-2 )(1+1/δ(G)-1),则G是λ'-最优的。并由此推出,若连通无三角图G的最小度δ(G)≥n/4+1,则G是λ'-最优的。最后给出例子说明这些结果给出的边界都是紧的。 相似文献
13.
设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-最优图的一个充分条件. 相似文献
14.
图是极大限制边联通的充分条件 《山东科学》2015,28(3):80-83
设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限制边连通的。 相似文献
15.
图是λ4-最优的一个充分条件 总被引:1,自引:0,他引:1
设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). 相似文献
16.
互联网络常以有向图或无向图作为模型,有向图的限制弧连通性能精确度量网络的容错性和可靠性.称有向图D的一个弧子集S是D的限制弧割,如果D-S中存在一个非平凡的强连通分支D1使得D-V(D1)包含至少一条弧.若强连通的有向图D存在限制弧割,则称D是λ′-连通的.λ′-连通图D的最小限制弧割所含的弧数称为D的限制弧连通度,记λ′(D).设D的围长为g,任取长度为g的有向圈Cg=u1u2…ugu1,令ξ(Cg)=min{(sum from i=1 to g)d+(ui)-g,(sum from i=1 to g)d-(ui)-g}且ξ(D)=min{ξ(Cg)}.本文给出了强连通有向图D是λ′(D)≤ξ(D)的一个充分条件. 相似文献
17.
设G是简单有限无向连通图,p,q是两个正整数.G的一个边割(顶点割)S是一个p-q-边割(p-q-顶点割),如果G-S不连通,且G-S中有一个分支至少含有p个顶点,另一个分支至少含有q个顶点.G称为λp,q-(kp,q-)连通的,如果一个p-q-边割(p-q-)顶点割存在.用λp,q(G)(kp,q(G))表示最小p-q-边割(p-q-顶点割)的基数.文章证明了在kp,q-连通(p≤q)和λp,p-连通图G中,使kp,q(G)≤λp,p(G)成立的一些充分条件及k1.p-连通图的一些性质. 相似文献
18.
图的λ3最优性的充分条件 总被引:7,自引:4,他引: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最优性的一个充分条件. 相似文献
19.
20.
m-限制边割将连通图G分离成阶不小于m的连通分支,图G的最小m-限制边割所含的边数称为图G的m-限制边通度,记作λm(G).对于包含m-限制边割的连通图G,有λm(G)≤ξm(G)(m≤3);如果λm(G)=ξm(G),则称图G是极大m-限制边连通的.本文证明:当n≥7时,无向广义De Bruijn图UBG(2,n)是极大m-限制边连通的(m={2,3}). 相似文献