共查询到20条相似文献,搜索用时 578 毫秒
1.
设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是λ'-最优的。最后给出例子说明这些结果给出的边界都是紧的。 相似文献
2.
《山西师范大学学报:自然科学版》2017,(3)
图D是带有两个弧轨道的强连通有向图,D1与D2是图D在自同构Aut(D)作用在边集E(D)上的两个弧轨道,有:D1=D[E1];D2=D[E2]为D的两个弧传递部分.我们证明,图D的弧连通度等于最小度,并且图D的点连通度,当加入围长条件,如果满足g(G)≥δ(D)-1/δ(Di)+1;则κ(D)=δ(D),这里我们只考虑δ(Di)≥0(i=1,2)的情况,并且δ(Di)是Di的最小度;κ(D)是有向图D的点连通度. 相似文献
3.
用k1>0和δi表示图Gi(i=1,2)的连通度和最小度,给出了无向图强乘积的连通度一个下界κ(G1(□×)G2)≥min{κ1(1+δ2),k2(1+δ1)}. 相似文献
4.
刘一平 《南京师大学报(自然科学版)》1987,(1)
1985年,M.M.Matthews和D.P.Sumner证明了:若G是二连通无爪图,且δ(G)≥1/3(p-2),则有Hamilton圈。本文证明了:若G是二连通无爪图,且对手G的任意两个不相邻的顶点u和v,有d(u)+d(v)≥2/3(p-2),则G有Hamilton圈。 相似文献
5.
6.
设G=(V,E)是一个连通图.边集SE,如果G-S不连通且G-S的每个连通分支至少有2个点,则称S是一个限制性边割.限制性边连通度λ′(G)就是G的最小限制性边割的基数.如果限制性边割存在,则称G是λ′-连通的.如果λ′(G)=ξ(G),则G是λ′-最优或者极大限制性边连通的,其中ξ(G)=min{|[X,Y]|:XV,|X|=2,G[X]连通}.图G的逆度是指R(G)=∑_v∈V 1/d(v).在此基础上,主要得到了:如果G是λ′-连通围长大于等于5的n阶图,且δ(G)≥2,如果R(G)小于某个关于最小度和顶点数的值,则G是λ′-最优的.对于不含钻石的图也得到了类似的结果. 相似文献
7.
利用矩阵的相似变换,研究了简单连通图的谱半径的可达下界,得到一个新的下界ρ(G)≥δ1+t-s+√(s+t-δ1)2+4s(δ2-t)/(2),等号成立当且仅当G(~)/(=)G1(~)/▽G2,其中G1为n-I阶(δ1-s)-正则图,G2为I阶t-正则图. 相似文献
8.
为精确估计网络的可靠度,需要最优化其图模型的限制边连通度.证明了: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-最优的. 相似文献
9.
设G是不含相交4-圈的平面图.证明了若G是连通图且最小度δ(G)≥2,则G包含一条边xy使得d(x)+d(y)≤9或一个2-交错圈.由这一结果得到G的线性2-荫度la_2(G)≤「Δ/2┐+6. 相似文献
10.
《太原师范学院学报(自然科学版)》2017,(3)
设G是n阶连通、局部连通无爪图,1)若■v∈V(G),d(v)=2,n≥9,则G有两个分支的2-因子;2)δ(G)≥3,n≥7,则G有两个分支的2-因子. 相似文献
11.
12.
13.
优美图是图论中的一个重要分支,至今对非连通优美性的研究并不多,特别是对n个图的并图的优美性研究就更少.本文证明了任意n个完备二分图的并图是优美图,且是交错图. 相似文献
14.
给出图∪ni=1Fmi,4 的一类非连通图 ,并证明这类图是优美图 ,且也是交错图 . 相似文献
15.
再论图Pn^3的优美性 总被引:3,自引:0,他引:3
给出图Pn3的另一种优美标号,证明其图是优美图且是交错图.另外指出文献[1]中的一个错误和给出了相应正确的结果,同时证明了严谦泰,张忠辅给出的标号以及我们改正的标号都是交错的. 相似文献
16.
优美图是图论中的一个重要分支,至今对非连通优美性的研究并不多,特别是对n个图的并图的优美性研究就更少.本文证明了一类任意n个二分图∧C4,m的并图4,1inmiC=U∧是优美图,且是交错图. 相似文献
17.
关于Km,n并图的优美性 总被引:2,自引:0,他引:2
对于自然数k,m,n,本文给出一类非连通图↑k∪↓i=1Kmi.ni;通过构造标号函数的方法,证明了当max{mi,ni}≥3,min{mi,ni}≥2(i=1,2,…,k)时这类图既是优美图,也是交错图;从而给出构造一类任意个图的并图是优美图的一种方法,拓宽了优美图及其应用的道路。 相似文献
18.
杜万根 《烟台大学学报(自然科学与工程版)》2013,26(4)
棱柱图(~P)n是由2个回路v1,v2,v3,…,vn和u1,u2,u3,…,un,加上边uivi后所组成的图形.图n∪i=1(~P)4是n个(~P)4的不交并图,图n∪i=1(~P)8是n个(~P)8的不交并图,证明了2类非连通图n∪i(~P)4和n∪i=1(~P)8是优美图且是交错图. 相似文献
19.
杜万根 《烟台大学学报(自然科学与工程版)》2013,(4):240-242
棱柱图n是由2个回路v1,v2,v3,…,v n和u1,u2,u3,…,un,加上边uivi后所组成的图形.图∪ni=14是n个4的不交并图,图∪n i=18是n个8的不交并图,证明了2类非连通图∪n i=14和∪n i=18是优美图且是交错图. 相似文献