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

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

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

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

k-连通无爪图中存在哈密尔顿圈的一个隐度条件

文中给出了强基本独立集的概念,并证明了如下定理:设G是一个具有n个顶点的k-连通无爪图,其中k≥2.如果对任意一个具有k个顶点的强基本独立集S,都有max{d2(x)|x∈S}≥n 2,则G是哈密尔顿图.此定理在无爪图的条件下推广了已有的几个有关图中哈密尔顿圈存在性的定理.     

关于无爪图中（u,v）—5路存在性的两个定理

证明了下列结果：（１）设Ｇ是３连通无爪图,│Ｖ（Ｇ）│≥６且Ｇ的每个导出图Ａ都满足φ（ａ１,ａ２）那么对任意ｕ,ｖ∈Ｖ（Ｇ）,若２≤ｄ（ｕ,ｖ）≤５,则对满足ｄ（ｕ,ｖ）≤ｋ≤５的整数ｋ,Ｇ中存在（ｕ,ｖ）－ｋ路（２）设Ｇ是３连通无爪图,│Ｖ（Ｇ）│≥６,且Ｇ的每个导出子图Ａ都满足φ（ａ１,ａ２）而Ｐ＝ｖ１,ｖ２,．．．ｖ５（ｖ１＝ｕ,ｖ５＝ｖ）是Ｇ的（ｕ,ｖ）－４路Ｇ（Ｖ（Ｐ）＝Ｋ│ｖ（ｐ）│则     

强半无爪图的完全圈可扩性

证明了连通局部连通的强半无爪图是完全圈可扩的．从而推广了Oberly D,Sumner D,Clark L,Hendry G R T等的相关结果．     

半无爪泛圈图的一个充分条件

本文证明了如果G是2-连通半无爪图,G不是圈,|V(G)|≥9,G的每个导出子图B满足φ(u,v)且G中不含同构于Z′的导出子图,则G是泛圈图.     

k-连通半无爪图的Hamilton性质

半无爪图是包含无爪图的更大的图类。关于k-连通半无爪图,得到以下结果:G是k-连通的半无爪图(k≥2),如果对于G2的任意基数为k 1的独立集X,都有∑d(v)≥n-k,则G是Hamilton图。     

Duffus闪的结果的一个推广

证明了下述结果：设Ｆ是度序列为（１，１，１，３，３，３）的简单图，Ｆ中度为１的点记为ａ１，ａ２，和ａ３；Ｇ为连通无爪图。若Ｇ的每一个与Ｆ同构的导出子图均满足性质φ（ａ１，ａ２）和φ（ａ１，ａ３），或φ（ａ１，ａ２）和φ（ａ１，ａ３）和φ（ａ２，ａ３），则Ｇ有哈密顿路。     

无爪图的泛连通性

证明了如果G是3连通无爪图,且G的每个导出子图A、子图T都满足φ（α、α2）,则G是泛连通图（当u、v∈V（G）,d(u,v)=1时;G中可能不存在（u,v）-k路,k=2,3,4除外）。     

半无爪图中的路因子

证明了如果G是一个半无爪图且它的最小度不小于d,那么G有一个路因子满足每条路的顶点数不小于d+1。     

距离无爪图的Hamilton性

距离无爪图类属于无爪图类。所谓距离无爪图是对图中的每一个顶点,其距离为的邻域的独立数均不超过3的图.F.BruceShephed已证明:若G是距离无爪图且G是2─连通的,则G有Hamilton路;若G是距离无爪图且G是3─连通的,则G有Hamilton圈.本文在此基础上,定义了一种新的禁用子图──网全爪,首先证明了2-连通的、无网的距离无爪图有Hamilton圈.又证明了2-连通的有网、无网全爪的距离无爪图有Hamilton圈.     

一类无爪泛圈图

本文证明了如下结果:G 是 n(≥8)阶,2—连通无爪图,且对 G 的每一个生成子图 A、A~+,满足(a_1,a_2),则 G 为泛圈图(除圈外)。     

哈密尔顿图的一类新的局部化充分条件

设L为图G的一个导出子图 ,若有 x ,y∈V(L) ,只要dL(x ,y) =2就有max{dG(x) ,dG(y) }≥ |G| / 2 ,则称L有局部Fan性质 .该文证明了以下结果 .G是一个 2_连通的 {K1.3 ,B1} -free图 .对任意一个整数s≥ 0 ,若G的任一个导出子图L∈ {Bi,0≤i≤s;Zs+2 }均有局部Fan性质 ,则G是Hamiltonian图 ,除非s=2且G H9.由此得到每个 2_连通的 {K1.3 ,Bi,0≤i≤s;Zs+2 }_free图除s =2且该图同构于H9外 ,均为Hamiltonian图 .     

无爪图过特殊子图的路

设Ｇ是ｋ－连通无爪图，Ｓ是Ｇ的子图，Ｇ中过Ｓ所有顶点的路称为Ｓ－路，证明了：若ａ３（Ｓ）≤ｋ＋１，则Ｇ含Ｓ－路，这里ａ３（Ｓ）为Ｓ的在Ｇ中两两离至少为３的顶点的最大数目，推广了如下结论：若ａ（Ｇ＾２）≥ｋ＋１，则Ｇ是可迹的，这里Ｇ＾２为Ｇ的平方图。     

无爪图的泛连通性

证明了如果G是 3连通无爪图 ,且G的每个导出子图A、子图T都满足(a1,a2 ) ,则G是泛连通图 (当u、v∈V(G) ,d (u ,v) =1时 ;G中可能不存在 (u ,v) -k路 ,k =2 ,3,4除外 )。     

2-连通半无爪图的可迹性

若对图G中任意一对距离为2的顶点x,y,存在u∈N（x）∩N（y）使得N[u]（真包含于）N[x]∪[y],则称G是半无爪图,对半无爪图证明以下结果：若G为n阶2-连通半元爪图,满足NC≥n -2/2,则G是可迹的。     

TT-′free图的最长圈

本文提出了两类新的禁用子图T和T′.一个图G称为TT-′free图,若G中不含同构于T或T′的导出子图,它是比无爪图更广的一个图类.G的一个圈C称为控制圈(简记为D-圈),若E(G-C)=Φ.本文证明了:顶点数不小于3的连通、局部连通TT-′free图G最长圈为D-圈,且G是局部泛圈的.     

TT''''-free图的最长圈

本文提出了两类新的禁用子图T和T＇.一个图G称为TT＇-free图,若G中不含同构于T或T＇的导出子图,它是比无爪图更广的一个图类.G的一个圈C称为控制圈（简记为D-圈）,若E（G-C）=φ.本文证明了：顶点数不小于3的连通、局部连通TT＇-free图G最长圈为D-圈,且G是局部泛圈的.     

Duffus等人的结果的一个推广

证明了下述结果：设Ｆ是度序列为（１，１，１，３，３，３）的简单图，Ｆ中度为１的点记为ａ１，ａ２和ａ３；Ｇ为连通无爪图．若Ｇ的每一个与Ｆ同构的导出子图均满足性质（ａ１，ａ２）和（ａ１，ａ３），或（ａ１，ａ２）和（ａ２，ａ３），或（ａ１，ａ３）和（ａ２，ａ３），则Ｇ有哈密顿路．     

无哈密尔顿路图的某些图

图G的路图P_k(G)是依下述方法得出的图:以G中的有k个顶点的路P_k作为顶点,且两个顶点相邻当且仅当对应的P_k的并是G中的路P_(k-1)或圈C_k。本文给出了下列结论:1)不存在最大度大于3且具有哈密尔顿P_(3-)图的树;2)不存在最大度大于3且具有哈密尔顿P_(3-)图的单圈图;3)给出了最大度为4且有哈密尔顿P_(3-)图的单圈圉的特征,因而证明了由H.J.Broersma和C.Hoede提出的两个猜测。