哈密尔顿图和邻域并

引用邻域并对哈密尔顿图进行研究，得到一些结果。

哈密尔顿图和邻域并

邻域并条件是近十年来研究哈密尔顿图的得力工具之一。本文得到距离是2的点对的邻域并条件 下的哈密尔顿图结果:若2连通 n ≥ 3 阶图 G 距离是2的任意两点 x,y 均有 |N(x) ∪ N(y)| ≥ (2n ? 4)/3,则 G 是哈密尔顿图或 G ∈ {G2 : 3K( n?2)/3,K(n?2)/3: K(n+1)/3: K(n+1)/3,Kn/ 3 Kn/ : Kn/ }。此结果改进一些已知结果。 3

泛连通图和邻域并条件

刻划2连通图在条件NC≥n-δ+1下的Pnm泛连通图性.得到结果:2连通n阶图G,若NC≥n-δ+1,则G是Pn6泛连通图或G2:(Ks+Kh).

点泛圈性的邻域并条件

该文利用邻域并条件讨论图的点泛圈性，证明了当ｍｉｎ｛｜Ｎ（ｕ）∪Ｎ（ｖ）｜ｕ，ｖ∈Ｖ（Ｇ），ｕｖＥ（Ｇ）｝≥２ｎ３＋１时，２－连通ｎ（≥１４）阶图Ｇ是［６，ｎ］－点泛圈的．并讨论了无Ｃｌ（３≤ｌ≤５）的几种情况，从而得到此条件下的点泛圈性的较完整的结果．

邻域并和[a,b]-覆盖图

设ａ≤ｂ是整数，Ｇ＝（Ｖ（Ｇ），Ｅ（Ｇ））是一个图。Ｇ的一个支撑子图Ｆ称为Ｇ的一个［ａ，ｂ］＿因子，若对任意的ｖ∈Ｖ（Ｇ），有ａ≤ｄＦ（ｖ）≤ｂ．图Ｇ称为是［ａ，ｂ］＿覆盖图，若对Ｇ的每一条边，存在Ｇ的一个［ａ，ｂ］＿因子包含它．本文给出了一个图是［ａ，ｂ］＿覆盖图的关于领域并的充分条件，得到了下列结果：设１≤ａ＜ｂ是整数，Ｇ是一个阶为ｎ的图，最小度δ（Ｇ）≥ａ且ｎ≥２（ａ＋ｂ）（ａ＋ｂ－１）＋１ｂ．如果对于Ｇ的任意两个不相邻的顶点ｕ，ｖ有｜ＮＧ（ｕ）∪ＮＧ（ｖ）｜＞ａｎ＋１ａ＋ｂ，则Ｇ是一个［ａ，ｂ］＿覆盖图．

邻域并与[a,b]-k-对等图

设G是一个n阶图,1≤a<b及b≥k≥0是整数,本文证明了若n≥2(a+b)(a+bb-1)+2k,图G的最小度δ(G)≥a+k,且NG(x)∪NG(y)≥ana++2bk,则G是[a,b]-k-对等图,推广了已有的结果。

哈密顿图的邻域交和邻域并条件

记δ和α分别为图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等人和尹家洪的结果。

邻域并和[a,b]-因子

设ａ＜ｂ是整数，Ｇ＝（Ｖ（Ｇ），Ｅ（Ｇ））是一个图．Ｇ的一个支撑子图Ｆ称为Ｇ的一个［ａ，ｂ］－因子，若对任意的υ∈ＥＶ（Ｇ），有ａ≤ｄ_Ｆ（υ）≤ｂ．本文得到了下列结果：设１≤ａ≤ｂ是整数，Ｇ是一个阶为ｎ的图，最小度δ（Ｇ）≥ａ且＞（ａ＋ｂ）（２ａ＋２ｂ－３）如果对于Ｇ的任意两个不相邻的顶点ｕ，υ有Ｎ_Ｇ（ｕ）ＵＮ_Ｇ（υ）≥ａｎ，则Ｇ有一个［ａ，ｂ］－因子．

具有邻域并型的 X-可迹图

设Ｇ是连通图，ＸＶ（Ｇ），若Ｇ存在路Ｐ使得ＸＶ（Ｐ），则称Ｇ是Ｘ－可迹图；记ＮＣ２（Ｘ）＝ｍｉｎ｛｜Ｎ（ｕ）∪Ｎ（ｖ）｜：ｕ，ｖ∈Ｘ且ｕｖＥ（Ｇ）｝，我们得到如下结果：如果Ｇ是ｎ阶２－连通图，ＸＶ（Ｇ）并且ＮＣ２（Ｘ）≥ｎ－１２，则Ｇ是Ｘ－可迹图，该结果在可迹图方面推广了Ｂ．Ｊ．

泛圈图的邻域并

让NC2 =min{ N(x) ∪N(y) x ,y∈V(G) ,d(x ,y) =2 } ,得到的主要结果如下 :对于 2连通n(n≤ 6 )阶图G ,如果NC2≥n-δ,则G是泛圈图或kn/2 ,n/2 .此结果改进了图论专家R .J .

图为Hamilton连通的邻域并或Fan型条件

图为Ｈａｍｉｌｔｏｎ连通的邻域并或Ｆａｎ型条件顾国华，孙学红（东南大学数学力学系南京２１００１８）（南京气象学院南京２１００４４）１定义与基本定理在文［１］中，Ａ，Ｂｅｎｈｏｃｉｎｅ，和Ａ．Ｐ．Ｗｏｊｄａ，证明了ｎ阶３连通图Ｇ，若任意两个距离为２的顶...

Ore型和邻域并条件定理的一个注记

设NC=min{|N(x)∪N(y)|;x,Y∈V(G),xy∈E(G)}。1990年美国乔治亚州立大学的陈冠涛教授给出一个哈密尔顿图的充分条件:若2连通n阶图G的不相邻的任意两点x、Y均有2|N(x)∪N(y)|+d(x)+d(y)≥2n-1,则G是哈密尔顿图。这是一个统一Ore条件和邻域并条件的新条件,此处给出了此定理的一个简单证明。

Hamilton连通性和邻域并条件

设 G =( V,E)为简单图 ,δ为图 G的最小度 ,1 987年 Faudree等人给出 N C=min{| N( x)∪ N ( y)‖ x,y∈ V( G) ,xy∈ N ( G) },有关文献曾研究 3连通的 H连通图 ,本文进一步得到 :若 G是 n阶 2连通图 ,且 N C≥ n -δ,则 G除几个图外均是H连通图 .从而 ,完成了邻域并条件的

1-坚韧图中具有邻域并型的X-最长圈

设 G是连通图 ,X V( G) ,G[X]是 G的 X生成子图 .记α( X) =max{|S|:S是 G[X]的顶点独立集 },σk( X) =min{ ki=1d( vi) :{v1,v2 ,… ,vk}是 G[X]的顶点独立集 },N Ck( X) =min{|∪ki=1N ( vi) |:{v1,v2 ,… ,vk}是 G[X ]的顶点独立集 }( k≥ 2 ) .本文得到如下结果 :对于 n阶的 1 -坚韧图 ( n≥ 3 ) ,X V( G)且σ3 ( X )≥ n+r≥ n,r为正整数 ,则存在一个圈 C满足 |C( X ) |≥ min{|X|,|X|+N Cr+ 5+ε(n+ r) ( X ) -α( X ) },其中ε( i) =3 13 i -13 i.此结果推广了 H.J.Broersma等在文献 [2 ]中的结果 .

数理科学与化学——哈密尔顿连通图和邻域并条件(Ⅰ)

记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=φ。

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

利用插点方法,研究图的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是哈密尔顿图.

图的邻域并和连通的[k,k+1]-因子

设G是阶为n的图.F是G的支撑子图且对所有的x∈V(G)都有k≤dF(x)≤k+1,则称F为G的[k,k+1]-因子.一个[k,k+1]-因子如果连通,则称为连通的[k,k+1]-因子.一个[k,k+1]-因子若包含一个哈密顿圈,则称为哈密顿[k,k+1]-因子.给出了图有哈密顿[k,k+1]-因子或连通的[k,k+1]-因子关于邻域并的若干新的充分条件.

邻域并与D_λ-圈

设图 Ｇ 是一个ｎ 阶简单图， Ｇ 中的一个圈 Ｃ 称为 Ｄλ圈，如果 Ｇｗ Ｖ（ Ｃ）的每个连通分支的阶都小于整数λ，如果 Ｇ 是 ２连通图，且 Ｎ Ｃλ（ Ｇ）≥ ｎ２ － ２（λ－ １），则 Ｇ 含有 Ｄλ圈或 Ｇ 是 Ｐｅｔｅｒｓｅｎ 图或 Ｇ

邻域并和[a,b]-消去图

本文给出了一个图是 [a,b]-消去图关于邻域并的充分条件。

邻域并和[a,b]—对等图

证明了如下结论 :设 1≤a <b是整数 ,G是n阶图 ,δ(G)≥a + 1且n≥2 (a +b) (a +b -1) + 1b .如果对于G的任意两个不相邻的顶点u ,v有 |NG(u)∪NG(v) | >an + 1a +b,则G是 [a ,b]—对等图 .