共查询到18条相似文献,搜索用时 93 毫秒
1.
2.
葛仁福 《徐州师范大学学报(自然科学版)》2002,20(3):15-18
Let S^23 denote an independent set with mini dist (u,v)|u, v∈S} = 2 and |S|=3. Our main result is the following theorem: Let G be a 3-connected graph of order n such that d(u) d(v) d(w)≥n 1 |N(u)∩N(v)∩N(w)|for any independent set S^23={u,v,w}, then G is Hamilton-connected. 相似文献
3.
记G=(V,E)是简单图,δ表示图G的最小度,NC=min{|N(x)∪N(y)|:x,y∈V(G)mxt∈E(G)|,NC2=min{|N(x)∪N(y)|:x,y∈V(G),d(x,y)=2},1989年Faudree等证明了:若3连通n阶图G,NC≥(2n 1)/3,则G是哈密尔顿连通图。据此进一步研究NC2≥(2n 1)/3,而且研究到2连通图,得到下面结果:若2连通n阶图G,NC2≥(2n 1)/3,则G是哈密尔顿连通图或G=ψ。 相似文献
4.
记δ和α分别为图G=(V,E)的最小度和独立数,1991年Faudree等人和尹家洪分别得到:“若2连通n阶图G的不相邻的任意两点x、y均有|N(x)∪N(y)|≥n-δ,则G是哈密尔顿图”和“若2连通n阶图G的长为2的任意两点x、y均有|N(x)∪N(y)|≥n-δ,则G是哈密尔顿图”。这里得到结果:若2连通n阶图G的满足1≤|N(x)∩N(y)|≤α-1的不相邻的任两点x、y均有|N(x)∪N(y)|≥n-δ,则G是哈密尔顿图。此结果推广Faudree等人和尹家洪的结果。 相似文献
5.
邻集交和边泛圈性质朱卓宇吴宗玉**(南京动力高等专科学校,南京210042)(南京炮兵学院,南京211132)本文用G表示n(≥3)阶简单无向图,用α表示图的独立数,其它概念和术语见文[1,2].文[3]利用邻集交和独立数α的关系研究图的点泛圈... 相似文献
6.
设a≤b是整数,G=(V(G),E(G)是一个图。G的一个支撑子图F称为G的一个[a,b]-因子,若对任意的υ∈V(G)有a≤dF(υ)≤b,图G称为是[a,b]-覆盖图,若对G的每一条边,存在G的一个[a,b]-因子包含它。本文给出了一个图的[a,b]-覆盖图的关于领域并的充分条件,得到了下列结果:设1≤a〈b是整数,G是一个阶为n的图,最小度δ(G)≥α且n≥2(a+b)(a+b-1)1/b如 相似文献
7.
记G=(V,E)是简单图,δ表示图G的最小度,NC=min{|N(x)∪N(y)|:x,y∈V(G),xy(?)E(G)},NC_2=min{|N(x)∪N(y)|:x,y∈V(G),d(x,y)=2}。1989年Faudree等证明了:若3连通n阶图G,NC≥(2n+1)/3,则G是哈密尔顿连通图。据此进一步研究NC_2≥(2n+1)/3,而且研究到2连通图,得到下面结果:若2连通n阶图G,NC_2≥(2n+1)/3,则G是哈密尔顿连通图或G=φ。 相似文献
8.
令G(V,E)是简单图,Ore研究了不相邻两点情况的哈密尔顿连通图。本中,我们进一步研究较好条件的长为2点的哈密尔顿连通图情况。结果不仅比Ore的好而且证明方法更加简单。 相似文献
9.
本文研究的图是简单图G ,限于本文的使用 ,记Fan =min{max{d(x) ,d( y) }|d(x ,y) =2 }.Fan定理[1 ] 2连通n阶图G ,Fan≥n/2 ,则G是哈密尔顿图 (H图 ) .证明 假设G不是H图 .记G的一最长圈为Cm:X1 X2 …XmX1 ,因G是 2连通的 ,记Xi,Xj 为和G -Cm 的一分支G1 中 y1 ,y2 相邻的两点 ,且满足 {Xi+1 ,Xi+2 ,… ,Xj- 1 }中没有点和G1 中点相邻 .情况 1 d( y1 ) <n/2 ,且d( y2 ) <n/2 .此时由Fan≥n/2 ,知d(Xi+1 )≥n/2 ,d(Xj- 1 )≥n/2 ,因Cm 为最长圈 ,所以 ( … 相似文献
10.
11.
12.
王冬冬 《徐州师范大学学报(自然科学版)》1997,(4)
设G是n阶3-连通无向简单图,α表示图的独立数.若对G的所有距离为2的顶点u,v,都有d(u)+d(v)≥n或|N(u)∩N(v)|≥α,则G是Hamilton连通的,除非G属于一个特殊图类. 相似文献
13.
方冬云 《莆田高等专科学校学报》2009,(2):40-42
通过探讨第一、第二数学归纳法,反归纳法,跳跃归纳法和双重归纳法在图论证明中的应用,说明数学归纳法在图论中对相关命题的证明不失为一种行之有效的方法。 相似文献
14.
讨论了特殊的 4k(k >1)个结点的简单图中存在Hamilton回路的充分性 ,并由此提出 :具有 4k个结点的 (2k - 1)正则简单图都是Hamilton图 . 相似文献
15.
设n≥3阶1—坚韧图,若对于G中任意导出爪K(1.3)或变爪K(1.3)+e上的三点u,v,w,且d(u,v)=d(u,w)=2,均满足|N(u)∩N(v)|≥-α-1或|N(u)∩N(w)|≥α-1,则G是Hamilton图。 相似文献
16.
利用非负矩阵理论并结合图论性质,给出图谱理论中3个重要定理的证明,给出的证明方法比之前文献的证明更为简洁、易懂. 相似文献
17.
18.
Win于1982年证明了2n阶Ore-(1)型图有边不交的3个1-因子.本文改进这个结果,得到一个新的充分条件:2n(n≥10)阶2-连通Ore-(-2)型图G有边不交的1个Hamilton图和1个1-因子,除非G是附图中所示的图之一. 相似文献