对Hamilton图性质的一个改进

n阶图G称为Hamilton图是指G包含一个长为n的圈,Bollbás曾证明了在Hamilton图H中,若边数e(H)≥n24-n+59,则H必含长为(n-1)的圈或具有特殊结构的长为(n-2)的圈.我们认为条件e(H)≥n24-n+59可以进一步减弱,本文证明了在e(H)≥n24-n+15的条件下,结论同样成立.     

k连通［s,t］图的Hamiltion连通性

若图G的任意个s顶点的导出子图至少有t条边,则称图G为[s,t]图．[s,t]图的概念可视为图的独立数概念的推广．本文证明：若图G是k连通[k＋1,2]（k≥2）图,则G或者是Hamilton连通的或者同构于Kk∨Gk．由此可以推出,若图G的阶是n（n≥3）,α（G）≤κ（G）－1,则G是Hamilton连通的．     

图的谱半径和Hamilton性

从图G的闭包理论角度去研究图的Hamilton性。利用图的补图谱半径的界，讨论了Hamilton图存在的谱条件，证明了n阶图G，如果它的补图的谱半径小于或等于（n-3）的算术平方根，则G是Hamilton图。     

一个新的充分条件和Hamilton图

在前人工作的基础上,创立进一步的新条件,得到结果:记δ为图G的最小度,若2连通n阶图G的距离为2的任意两点x和y均有max{d(x),d(y)}≥n/2或|N(x)∪N(y)|≥n-δ,则G是Hamilton图.     

关于Hamilton图的新的圈结构定理

设G是一个n阶图,若对于每一个k (3≤k≤n),图G都含有k-圈,则称图G为泛圈图.泛圈图是圈理论研究中的重要课题.研究得到了Hamilton圈上两个不相邻的点在圈上的距离是3的泛圈性结果.     

Ore条件弱化下的Hamilton性

让G(V,E)是n阶图,在Ore条件下,即G的不相邻的任意两点x,y均有d(x)+d(y)≥n,则G是Hamilton图.进一步考虑G的不相邻的任意两点x,y均有d(x)+d(y)≥n-1,和长为2的任意两点x,y均有d(x)+d(y)≥n-1,两个条件下G的Hamilton性.     

Hamilton二部图的一个充分条件

证明了当设G=(X,Y;E)是连通二部图,｜X｜=｜Y｜=n!5,且δ(G)≥2,若NC2≥n-1,则G是Hamilton图。     

一类亚几乎唯一泛圈图

设G是阶为n的简单Hamilton图,若存在不同的p,q(3≤p相似文献   

线图泛圈性的一个充分条件

本文的主要结果是：设G是n≥60阶连通图，且G是Hamilton图．若G满足下列条件之一（1）若g＝3且■e∈E（G），有d（e）≥（2n-9）／5，（2）若g≥4且■e1，e2∈E（G），e1与e2不相交，有d（e1）＋d（e2）≥2（2n-9）／5，则L（G）是泛图的。     

关于几乎正则2-连通图的Hamilton性的注记

研究几乎正则图的Hamilton性,得到了定理1　设G是2连通的(k,k 1)图,并且k≥V(G)3 13,如果G是偶数阶的图,则G是Hamilton图.定理2　设G是(k,k 2)图,并且k≥n3 103,如果存在G的一个非空独立集B1,使得B1≥n3-133,而且对于G的所有独立集B,都有B≤n2-1,则G是Hamilton图.