首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
一个图称为K1,n-free图如果它不含K1,n作为其导出子图.文中讨论了K1,n-free图有[a,b]-因子的一些充分条件.  相似文献   

2.
K1,n—free图的f—因子   总被引:2,自引:0,他引:2  
图G称为K1,n-free,若图G不包含同构于K1,n的导出子图。设f(x)是定义在V(G)上的非负整数函数,G的一个支撑子图F称为G的一个f-因子,若对任意的v∈V(G)有dF(v)=f(v),对K1,n-free图存在f-因子涉及到最小度条件进行了研究,得到了一个充分条件。有关定理为本定理的特例。  相似文献   

3.
证明了如下结果:设G是3—连通图,如果G满足如下之一:(i){K1,3,A,D)-free.(ii){K1,3,A,P5}-free.(iii){K1,3,I}-free.(iiii){K1,3,Z3,B}-free.则G是H-连通的.  相似文献   

4.
证明了如下结果,设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-连通的。  相似文献   

5.
图的升分解问题的两个新结果   总被引:2,自引:0,他引:2  
Alavi等人在1987年定义了图的一种新分解,即“升分解”(AscendingSubgraphDecomposition),并且猜想:任意有正数条边的图都可升分解.该文证明了下面两个新结果:(1)Hi是i条边的Kn的子图,当n+1≤i≤2n-2n/3[]2-2时,G=Kn-Hi可升分解为K1,1,K1,2,…,K1,n-5,K1,n-4,Gn-3(n≥6),其中K1,n-4Gn-3.(2)Hi是i条边的Kn的子图,当i≥2n-2n/3[]2时,G=Kn-Hi不一定有定理1形式的升分解.  相似文献   

6.
图的第二个最小特征值的界   总被引:2,自引:0,他引:2  
设G是n个顶点的简单图,λn-1(G)为G的第二个最小特征值。G的非孤立点形成的图记为G1,V(G1)=s,(3≤s≤n)。本文主要证明了:a.若G1不是完全偶图,则λn-1(G)≤λs-1(K2,s-2^-e),等式成立=G1≌K2,s-2^-^e。其中图K2,s-2^-^e为完全偶图K2,s-2去掉一边e而得到的图b.若G1既不是完全偶图,又不是K2,s-2^-e,则λn-1(G)<-√2/2  相似文献   

7.
所获主要结果是:设G是n≥3阶几乎无桥的简单连通图,G≌K1,n-1,若对G中任何互不相交的三条边e1,e2及e3有d(e1)+d(e2)+d(e3)≥2n+1则G有一个D-闭迹,从而L(G)是哈密顿图,此结果推广了Benhocine A等人的结果。  相似文献   

8.
一个图C=(V,E)是[l,m]-泛连通的,如果在G的任意一对节点x与y之间有长为K—1的路Pk(x,y),K=l,l+l,…,m。G具有性质P(K),如果对G的任何一对距离为2的节点x和y,有d(x)+d(y)≥K。作者探讨了一类产(K)图的路连通性,改进了Faudree-Schelp定理,得到两个定理:定理1设G=(V,E)是n阶P(n—1)图。如果G是[n—1,n]-泛连通的,则G是[8,n]-泛连通图(n≥8).定理2设G是3-连通n阶P(n)图。如果G的独立数α(G)<n/2,则G是[5,n]-泛连通图,n≥5.  相似文献   

9.
给出了抽屉图D(n1,j2,n2;j3,n3...;jm,nm)的定义及其顶点集的K-优美性的标号,所得结果不仅推广了(1)中定理1,而且推广了(2)中的结果。  相似文献   

10.
设G是一个简单图,f:V(G)→(1,3,5....),如何对G的任意n对集M,G-V(M)有一个(1,f)-奇因子,则称图G存在n-可扩充的(1,f)-奇因子,本文主要对n-可扩充图成立的一些结果进行了改进,证明了这些结果在有n-可扩充的(1,f)-奇因子的图中也成立。  相似文献   

11.
一个实用的检验Kn(3,p)的算法   总被引:2,自引:2,他引:0  
设Kn是n个顶点的完全图,若对Kn的每条边着以红色或蓝色,并且图中既不包含红色团K3也不包含蓝色团Kp,这样就得到一个二色边图Kn,同时将这种染色所得的图记为Kn(3,p),把使Kn(3,p)成立的最大值记为R(3,p),R(3,p)=r(3,p)-1,r(3,p)是Ramsey数,本给出一个实用的算法,可以对给定连通图检验Kn(3,p)是否成立 。  相似文献   

12.
利用不可约路的概念,证明了当Ps是不可约的路时,Kn-E(kPs∪rK3)是色唯一的图,其中设Kn-E(G)表示从完全图Kn中删去一个和G同构的子图的所有边而得到的图,s≠4,且ks+3r=n,k3是有3个顶点的完全图,同时给出了三类新的色等价图簇。  相似文献   

13.
完全三部图K(n- k,n,n)的色性   总被引:1,自引:1,他引:0  
设P(G,λ)表示简单图G的色多项式;若对任意简单图H 满足P(H,λ) = P(G,λ),都有H 与G同构,则称G是色唯一图;设K(m ,n,r) 表示完全三部图;本文证明了:(1) 若n > k + k2/3,则图K(n - k,n,n) 是色唯一的,(2) 若n ≥8,则K(n - 4,n,n) 是色唯一的;  相似文献   

14.
关于完全三部图K(n-k,n,n+k)的色性   总被引:2,自引:2,他引:2  
设G为简单图,P(G,λ)的色多项式,若对任意简单图H满足P(H,λ)=P(G,λ),都有H与G同构,则称G是色唯一图,设K(m,n,r)表示完全三部图,证明了:(1)对任意非负整数k,若n≥2√-3k/3+k^2,则K(n-k,n,n+k)是色唯一图。(2)若n≥9,则K(n-3,n,n+3)是色唯一图。  相似文献   

15.
设G为n阶连通图,且对G中任一对距离为2的顶点u、v,有d(u)+d(v)≥n,则称G为OF图.本文讨论了OF图的泛连通性,主要得到下列结果:设G为n阶OF图,则G为下列三类图之一:(1)G是[5n]-泛连通图(2)H+;(3)Km#Kn-m+2及其部分支撑子图,其中3≤m≤n-1,|V(H)|=.  相似文献   

16.
图的圈长分布和圈长分布唯一的图   总被引:1,自引:0,他引:1  
阶为n的图G的圈长分布是指序列(c1,c2,…,cn),其中ci是G中长为i的圈数.若不存在,使G’与G有相同的圈长分布,则称图G是圈长分布唯一图.本文确定了Kn-A(|A|=j,n≥|A|+3)的最小、最大的4圈和5圈数.证明了当n≥9时,Kn-A(|A|=4)以及当n≥14时,Kn-A(|A|=5)都是圈长分布唯一图.  相似文献   

17.
本文中我们获得泛连通图的一个结果。设G是n阶简单图,若 ≥ (n+1)/2,则G是泛连通图或G=K(n-1)/2  K(n+1)/2。此结果比1977年J· Williamson 得到的结果好。  相似文献   

18.
一个图若不含与K1,r同构的导出子图,则称它为无K1,r图,本文将运用T-插点方法,通过对图的独立集的邻域交的研究,给出(k+1)-连通无K1,r图Hamilton-连通的两个充分条件。  相似文献   

19.
分别给出了完全3部图K1,2,n和完全4部图K1,1,1,n的一种优美标号,从而证明了K1,2,n和K1,1,1,n是优美图.  相似文献   

20.
给出同阶(阶数≥7)树和不含K_3的(P,P+1)图可包装的充要条件为{G_1,G_2}不是下述图对之一:(1){S_n,G_2},其中Sn是n阶星图,G_2是无孤立点的(P,P+1)图;(2){S'_n,G_2},其中S'_n是由S(n-1)的任一边上增加一个剖分点得到的n阶树,G_2是最小度大于1的(P,P+1)图。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号