共查询到18条相似文献,搜索用时 62 毫秒
1.
2.
徐新萍 《南京师大学报(自然科学版)》1995,18(4):16-20
证明了如下结果,设G是3-连通图,如果G满足如下之一:(i){K1,3,A,D}-free,(ii){K1,3,A,P5}-free.(iii){K1,3,i}free.(iiii){K,1,3,Z3,B}-free.则G是H-连通的。 相似文献
3.
4.
5.
刻划了无环无向图的超边连通性(边连通性)与顶点最小度的关系。得到了边连通性、超边连通性的充分条件,并构造了非超边连通的图,由此表明定理1和定理2条件中的界是不能被改进的。 相似文献
6.
7.
一个图若不含与K1.3同构的导出子图,则称它为无爪图,本文利用T-插点方法,得到(k+1)-连通无爪图是Hamilton-连通的两个充分条件,(1)设G是(k+1)-连通无爪图(k≥2),若对每个X∈Ik+1(G)有s2(X)〉1,则是G是Hamilton-连通图,(2)设G是(k+1)-连通无爪图(k≥2),若对每个X∈Ik+1(G),有∑x∈xd(x)≥n(x)-k+1,则G是Hamilton 相似文献
8.
9.
研究了扩张竞赛图中的泛连通性点对的存在性问题。证明了如果传递的扩张竞赛图D不是竞赛图,那么D中不包含泛连通性点对。研究了扩张竞赛图中存在泛连通性点对的充分条件:证明了(a)设D1,D2,…,D1是连通但非强连通的扩张竞赛图D的一个强分支无圈序。若Di(i=1,2,…,f)有1一路一圈因子,则D中必存在泛连通性点对。午且找到泛连通性点对的时间复杂度为0(n^0.5).(b)设D是由连通但非强连通竞赛图r的强分支t(1y(t)1≥3)平衡扩张而成的,(当Iy(t)I=1时,Ti不变),则D中必存在泛连通性点对。 相似文献
10.
11.
孙志人 《南京师大学报(自然科学版)》1995,18(1):35-40
设G是k-连通无爪图,S是G的子图,G中过S所有顶点的路称为S-路,证明了:若a3(S)≤k+1,则G含S-路,这里a3(S)为S的在G中两两离至少为3的顶点的最大数目,推广了如下结论:若a(G^2)≥k+1,则G是可迹的,这里G^2为G的平方图。 相似文献
12.
何春阳 《盐城工学院学报(自然科学版)》2014,27(3):18-21
Nikiforov等人最近将图谱研究与极值图论相结合,提出了谱Turán型问题:给定一个图F,设G是一个不含子图与F同构的n阶图,那么图G的谱半径至多是多少?双圈图是边数等于顶点数加1的简单连通图。近期,部分学者对双圈图的谱半径进行了研究,确定了双圈图谱半径的第1~10大值和相应的极图。受此启发,研究了不含三圈的双圈图,确定不含三圈的双圈图的谱半径的上界,并刻画了相应的极图。 相似文献
13.
Euler生成子图边数的一个定理 总被引:2,自引:2,他引:0
证明了设G=(V,E)是2-边连通的简单图,| V |=n,δ(G)是G的最小度,若δ(G)≥max{4,n-4/5}时,G存在Euler生成子图H,使得| E(H)|/|E(G)|≥2/3;即此时Catlin的2/3--猜想成立. 相似文献
14.
周永生 《兰州理工大学学报》1987,(4)
本文得到了奇数度循环图是连通图的充要条件及C_n×k_2(krn/2)为循环图的充要条件,证明了三度连通循环图C_n同构于C_n<1,n/2>或C_n<2,n/2>。这一结果颇有意义。 相似文献
15.
对于图G的边e=uv,定义d(e)-d(u)+d(v),这里d(u)和d(v)分分别表示u和v的度,该文的主要结果是:对阶为n(n≥40)的简单连通图G,如果对G中任意两条边距离为2的边e1,e2都有d(e1)+d(e2)≥n,并且线图L(G)是Hamilton的,则L(G)是泛圈的,并且条件L(G)是Hamilton是必要的。 相似文献
16.
一类具有生成闭迹的图 总被引:1,自引:0,他引:1
乌力吉 《内蒙古大学学报(自然科学版)》1993,24(2):135-141
1987年,P.Paulraja在[2]中给出如下猜想:如果G是δ(G)≥3的2-连通图,且G的每条边均属于长为3或4的圈,则G有生成闭迹,同年P.A.Catlin在[3]中猜测上述的G还是可折迭的(Collapsible),本文给出了这两个猜想的证明。 相似文献
17.
党恺谦 《东北大学学报(自然科学版)》1996,17(5):568-570
设G为n阶2连通图,D(x)=(y│y∈V(G),d(x,y)≤2),(d1,d2,...,dj,...,d│D(x)│为D(x)中所有顶点的度排成的非减度序列dd(x)为(d1,d2,...,dj,...d│D(x)│)中当j=d(x)时的度,δ0=min(max(d(x),d(y))x,y∈V(G),D(x,y)=2),δi=min(dd(x)│x∈D(δi-1)│,D(δi-1)=(x│x 相似文献