共查询到19条相似文献,搜索用时 62 毫秒
1.
具有n个顶点的图G(n≥3)是k-可序哈密顿-连通的(k是整数,且2≤k≤n),如果对于G中每一个具有k个不同顶点的可序集合S={v1v2,…,vk},都存在G中的哈密顿路P包含S且不改变其中元素的次序.本文证明了:对于具有n个顶点的图G,u、v是G中任意两个不相邻的顶点,且d(u)+d(v)≥n+1.如果G是「k+1/2﹁-连通的k-可序图,k是整数且2≤k≤n/12,则G是k-可序哈密顿-连通图. 相似文献
2.
3.
夏维群 《同济大学学报(自然科学版)》1989,17(2):229-231
如果图G含有一个过G中每个顶点恰好一次的圈,则称G是一个哈密顿图。对于含有两个不相邻顶点a和b的图G,本文给出了一些条件,如果G满足这些条件,且G ab是哈密顿图,则G也是哈密顿图。 相似文献
4.
证明了如下结果:(1)若G是2-连通的(K1,3,P5,B)-自由图,或2-连通的(K1,3,Z2,P5)-自由图,则G是哈密顿图,(2)若G是3-连通的(K1,3,Z1)-自由图,或3-连通的(K1,3,Z2,P5)自由图,或3-连通的(K1,3,P5,B)-自由图,则G是哈密顿连通的。 相似文献
5.
刘红霞 《烟台大学学报(自然科学与工程版)》2006,19(2):79-82
既是κ-覆盖又是κ-消去的图称为κ-对等图.给出了边连通度为λ的r-正则图是后.对等图的若干充分条件,得到了如下结论:设r,κ,λ均为正整数,G是边连通度为λ的r-正则图,λ≥2且|V(G)|为偶数、若r/λ≤κ≤r-r/λ,则G是κ-对等图.设r为奇数,后为偶数,G边连通度为λ(G)=λ≥2的r-正则图,λ^*=2[λ/2]+1.若2≤κ≤r-r/A^*。则G为κ-对等图. 相似文献
6.
即是k-覆盖又是k-消去的图称为k-对等图.本文研究了有约束条件的r-正则图和k-对等图之间的关系,给出了有约束条件的r-正则图是k-对等图的关于顶点数和边连通度的充分条件. 相似文献
7.
证明了下面的结论:设G是n阶3-连通图,如果对任意满足dist(u,υ)=2的顶点{u,υ)(G),有max{d(u),d(υ)}+|N(u)∪N(υ)|≥n+1,则G是哈密顿连通的. 相似文献
8.
9.
Ando 证明了如果G是极小的k-连通图,且G中不含有K1 C4,若对于V(G)中的任意一个k度点x,与x关联的边中都存在一条不在三边形中的边,那么G中含有k-可收缩边.改进这个结果得出结论:如果G是极小的k-连通图,且不含图P,若G中任-k度点x,都存在与x关联的不在三边形中的边,那么G中有k-可收缩边. 相似文献
10.
二分图中k-因子存在的两个充分条件 总被引:1,自引:0,他引:1
钱建波 《山东大学学报(理学版)》2001,36(4):477-480
设G=(X,Y;E)为二分图,其中|
X |=| Y |=n为整数.证明了若 相似文献
11.
12.
平面三次图哈米尔顿性的一个充要条件 总被引:1,自引:1,他引:0
许寿椿 《中央民族大学学报(自然科学版)》2008,17(3):11-16
本文证明平面三次图Dg有哈米尔顿圈的充分必要条件是与之对偶的极大平面图g有树树型四着色.即Dg的对偶极大平面图g有四着色C,该四着色的某组对偶二色子图Gk的两个分支都是树.据此得到求出图Dg全部哈米尔顿圈的算法,该方法已经成功处理了批量例图. 相似文献
13.
曾建初 《贵州大学学报(自然科学版)》2004,21(2):124-126
证明了命题“竞赛图D=(V,E),顶点的个数|V|=n为奇数,对Vv∈V,d^ (v)=d^-(v)=n-1/2竞赛图是哈密顿图。” 相似文献
14.
施容华 《南京理工大学学报(自然科学版)》1992,(4)
从1952年Dirac定理开始,Hamilton图的充分条件通常沿着边密度条件发展。Ore定理放宽了Dirac条件而且推广了控制图中顶点度的方法;进一步,Fan定理打开了一个全新的研究道路——尽管还是稠密性条件,但渗入某些局部化结构。1989年,Faudree等人提出了邻域并条件,近几年许多新结果不断涌现。文中,我们推广了上述结果,提出新的Hamilton图的充分条件。 相似文献
15.
16.
17.
18.
设R是有单位元1的交换环,且1≠0.环R的单位凯莱图,记作Γ(R),是一个简单图,图的顶点是环R的所有元素,且两个互异顶点x与y相邻当且仅当x-y是R的单位即可逆元.该文证明了若有限环交换R不同构于模2的剩余类环Z_2,则环R的单位凯莱图Γ(R)是哈密尔顿图当且仅当Γ(R)是连通图. 相似文献
19.
石琳 《内蒙古大学学报(自然科学版)》1992,23(1):32-36
如果非平凡连通图G中任意的顶点v都对应G中唯一的顶点,使d(v,)=diam(G),则称G为平衡图.若平衡图G中由边uv∈B(G)可推出∈B(G),则称G为调和平衡图.本文证明了顶点数为n直径为d(d≥5)的调和平衡图G当G≌C_n时有关系式n≥3d. 相似文献