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

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

3-连通无爪图的度和与泛圈性

若图G中不含同构于k1,3的导出子图,则称G为无爪图.笔者讨论了3-连通爪图中三个顶点的度和与泛圈性之间的关系,给出了图是泛圈的一个充分条件,得到了如下结果:设图G是n阶3-连通无爪图,如果σ3(G)≥n+1,则G是泛圈的.     

无爪图中子图的度和与Hamilton圈

定义了子图的度的概念,证明了如下结果：设图G是n阶2-连通无爪图,如果G中任意两个同构于心的不相邻子图日,也的度和d（H1）＋d（H2）≥n-2,则G有Hamilton圈．     

连通、局部连通无爪图的2-因子

设G是n阶连通、局部连通无爪图,1)若■v∈V(G),d(v)=2,n≥9,则G有两个分支的2-因子;2)δ(G)≥3,n≥7,则G有两个分支的2-因子.     

拟无爪图的1-因子

拟无爪图是比无爪图更广泛的图类.在拟无爪图中有下面的结论：若G含有偶数个点且是连通的拟无爪图,则G包含1-因子.以上结果扩展了无爪图的相应结果.     

距离无爪图的Hamilton性

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

［s,t］-图泛圈性的一个充分条件

如果图G中任意s个点的导出子图至少含有t条边,则称图G为［s,t］-图。设G是2-连通［4,2］-图,且|G|≥7,G是泛圈图。     

同阶双轨道连通图的超圈边连通性

对于图G,如果G-F是不连通的且至少有两个分支含有圈,则称F为图G的圈边割.如果图G有圈边割,则称其为圈可分的.最小圈边割的基数叫作圈边连通度.如果去除任何一个最小圈边割,总存在一分支为最小圈,则图G为超圈边连通的.设G=(G_1,G_2,(V_1,V_2))为双轨道图,最小度δ(G)≥4,围长g(G)≥6且|V_1|=|V_2|.假设G_i是k_i-正则的,k_1≤k_2且G_1包含一个长度为g的圈,则G是超圈边连通的.     

子图的度与 Dominating 圈

笔者利用子图的度给出了如下结果：对2-连通无爪图 G，若任意同构于 K2的不相邻子图 H1，H2，H3满足：d（H1）＋d（H2）＋d（H3）≥｜G｜-1，则 G 的任意最长圈是 Dominating 圈。     

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是局部泛圈的.     

禁用两个子图的图的全控制数

设G=V(V,E)是一个简单无向图.一个点悬挂三个一度点的图称为爪图,D图是一个三角形其中两个点各悬挂一条长为2的路.如果图G的任何导出子图都不同构于爪图也不同构于D图,则称G为无爪和无D图.设S是V的非空子集,如果不在S的点一定与S中的某个点相邻,则称S为G的控制集.如果G中的点一定与S中的某个点相邻,则S称为G的全控制集.最小全控制集包含顶点的数目称为全控制数.给出了当G是N阶连通的无爪和无D图时全控制数紧的上界.     

(K1,4;2)-图的点泛圈性

证明了如下结论：设G是最小度至少是4的连通（K1,4;2）-图,如果G中爪心独立且G的每个同构于z1的导出子图具有性质Φz1（a,b1）或Φz1（a,b2）,则G是点泛圈的.本结论是无爪图的相关结果的推广.     

二连通、无爪图是Hamilton图的一个充分条件

1985年,M.M.Matthews和D.P.Sumner证明了:若G是二连通无爪图,且δ(G)≥1/3(p-2),则有Hamilton圈。本文证明了:若G是二连通无爪图,且对手G的任意两个不相邻的顶点u和v,有d(u)+d(v)≥2/3(p-2),则G有Hamilton圈。     

立方图中的路因子和圈因子

给定连通图集合Φ,对图G的生成子图F,如果F的每个分支都同构于集合Φ的一个元素,则F被称为G的Φ-因子.最近Kawarabayashi 等证明了:2-连通立方图有一个{Cn|n≥4}-因子和{pn|n≥6}-因子,其中Cn表示阶为n的圈,Pn表示阶为n的路.Kano等给出了每一个阶至少为8的立方偶图有{Cn|n≥6}-因子和{pn|n≥8}-因子的结论,并且提出猜想:阶至少为6的3-连通立方图有{Cn|n≥5}-因子和{pn|n≥7}-因子.现给出这个猜想的证明.     

3-连通[5,2]-图中的Hamilton圈

如果图G中任意s个点的导出子图中至少含有t条边,则称图G为[s,t]-图.本文证明了:若G是3-连通[5,2]-图并且|G|≥11,则G含有Hamilton圈.     

三角连通[4,2]-图的完全圈可扩性

如果G的任意s个点的导出子图中至少含有t条边,则称图G为[s,t]-图.本文证明了:若G是无孤立点的三角连通[4,2]-图,则G或者是完全圈可扩的或者同构于F.其中图F有与图■∨K2同构的导出子图.     

无爪图是准泛连通的一个新充分条件

设3—连通无爪图 G 是无 B 图.如果对 G 的任意的同构于 Z_2的导出子图有(?)(a_1,b_1)(?)(a_1,b_2),则 G 是准泛连通的。     

一类泛圈图

本文证明了如果G是2连通无爪图,G不是圈,n=|v(G)|>q,G的每个导出子图A都满足φ(a_1,a_2),且G中不存在W′作为其导出子图,则G是泛圈图。     

直径不超过2的无爪图的2-因子

Gould证明了直径不超过2的无爪图G是哈密顿的,也就是说,直径不超过2的无爪图G存在一个分支的2-因子.本文通过利用图G的哈密顿性及无爪图的特点即若G是无爪图且d(u,v)=2,则N(u)∩N(v)=J(u,v),分析了图G的结构,得到了G包含两个分支2-因子的一个充分条件.