关于图的哈密尔顿性的一些新的结果

关于哈密尔顿图和哈密尔顿连通的两个基本结果是Ore给出的:设G是一个n(n≥3)阶图,如果对于G的任意一对不相邻顶点u,v,有d(u) d(v)≥n或n 1,则G是哈密尔顿图或哈密尔顿连通的.设G是一个图,对于任意u∈V(G),令N(u)表示u的邻点集;对于任意U∈V(G),令N(U)=∪u∈UN(u).本文利用插点方法,给出了关于k或(k 1)-连通图(k≥2)G是哈密尔顿的,哈密尔顿连通的或1-哈密尔顿的统一证明.其充分条件是关于|N(S)| |N(T)|与n(S ∪T)的不等式,这里S,T是图G的任意两个不交的独立集,并且|S|=s,|T|=1,S∪T也是一个独立集,这里n(S∪T)=|{v∈V(G):dist(v,S∪T)≤2}|.     

关于图的哈密尔顿性的新的充分条件

设G是一个图,对于任意U()V(G),令N(U)=Uu∈UN(u),d(U)=|N(U)|.我们给出了两个结果:设s和t是正整数,G是(2s 2t 1)-连通图,且阶为n;若对于任两个强不交独立集ST,|S|=s,|T|=t,有d(S) d(T)≥n 1,则G是哈密尔顿连通的或1-哈密尔顿.     

连通、N_2-局部连通、K_(1,4)-受限图的哈密顿性

证明如下结论 :设G是连通、N2 -局部连通、δ≥ 6的K1 ,4 -受限图 ,如果G中不含有同构于G1 ,G2 或G3的导出子图H ,则G含哈密顿圈 .     

P3——支配图哈密尔顿性的一个充分条件

在文献[4]中作为半无爪图的一个超类,作者引进P3-支配图,并研究了这类图一些性质。设G是2-连通的P3-支配图,我们证明了G是哈密尔顿的一个充分条件局部连通型条件。     

哈密尔顿性，邻域并和部分平方图

利用插点方法,研究图的H-性,给出了k-连通图是哈密尔顿的充分条件:设G是k-连通图(k≥2),若对于每个Y∈Ik 1(G*),在G中,有σb(Y)=sum from i=o to k(|N(Yi)|>/(b k)/2(n(Y)-1) μ((b(2k-2b 1))/2-1) ,则G是哈密尔顿图.     

IMPLICIT DEGREES AND CHVATAL'S CONDITION FOR HAMILTONICITY

Based on the ideas in[9],an integer d~0(v),called the implicit degree of v whichsatisfies d~0(v)≥d(v),is associated with each vertex v of a graph G.It is proved that if theimplicit degree sequence d_1~0,d_2~0,…,d_n~0(where d_1~0≤d_2~0≤…≤d_n~0)of a simple graph G on n≥3vertices satisfiesd_i~0≤i相似文献   

本质集和1-几乎Hamilton性

设G是图 ,图G的独立集Z称为本质的 (简称本质集 ) ,如果存在 {z1 ,z2 } Z ,使得dist(z1 ,z2 ) =2 (这里dist(v,z)表示v与z间的距离 ) .结合插点方法以及 ∑ki=1N(Yi)和n(Y) (其中Y ={y1 ,y2 ,… ,yk}为G中任一独立集 ,Yi={yi,yi- 1 ,…yi- (b- 1 ) } Y ,i=1 ,2 ,…k,yi 的下标取模k,b(0 相似文献   

哈密尔顿性和部分平方图的独立集

设G是一个图,G的部分平方图G^＊满足V（G^＊）=V（G）,E（G^＊）=E（G）∪{uv：uv∈E（G）,且J（u,v）≠φ},这里J（u,v）={w∈N（u）∩N（v）,N（w）（∈）N[u]∪N[v]}.本文利用插点方法,给出了关于k,或（k＋1）-连通（k≥2）图G是哈密尔顿的,1-哈密尔顿的或哈密尔顿连通的统一证明.其充分条件是在图G中关于^k∑i=1｜N（Yi）｜＋b｜N（y0）｜与n（Y）的不等式,这里Y是图G的部分平方图G^＊的任一独立集,对于i∈{1,2,…,k},Yi={yi,yi-1,…,yi-（b-1）}（∈ ）Y（yj的下标将取模k）;b是一个整数,且0＜b＜k＋1;n（Y）=｜{v∈V（G）,dist（v,Y）≤2}｜.     

P3-支配图哈密尔顿性的两个充分条件

在文献[4]中作者引进P3-支配图,并研究了这类图的一些性质.设G是2-连通的P3-支配图,证明了G是哈密尔顿的两个充分条件fan型条件和禁止子图型条件.     

二维环面网络的边容错哈密尔顿性

网络的容错性是指当网络中出现故障时,该网络仍然具有的一些好的性质,它是衡量一个网络可靠性的重要标准。文章研究了二维网络的边容错哈密尔顿性,证明了在一种条件故障假设以及排除一种禁止圈的情况下,对给定的偶数k≥6,F是Torus-(k,k)中故障边的集合。若F中元素个数至多为4时,则Torus-(k,k)-F中仍存在哈密尔顿圈。