2-连通无爪图的连通因子

若图G不含有同构于K1,3的导出子图,则称G为一个无爪图.令a和b是两个整数满足2≤a≤b.本文证明了若G是一个含有[a,b]因子的2连通无爪图,则G有一个连通的[a,b 1]因子.     

包含子图K_4的无割点次极大图的唯一性

研究次极大图(即链环分支数等于基圈数的连通平图)的唯一性.证明了无割点且包含子图K_4的连通平图G是次极大图当且仅当G同构于K_4,并刻画了包含子图K_4的次极大图的结构.     

无爪图中点不相交的特殊四阶子图

如果图中不存在同构于K_(1.3)的诱导子图,则称这样的图为无爪图.令K_4~-表示从K_4中去掉一条边后得到的图.Faudree等人研究了无爪图中点不交三角形的个数与其最小度之间的关系,受此启发,我们研究了无爪图中点不交的K_4~-个数与其最小度以及阶数之间的关系.设G是阶数为n且最小度为δ≥5的无爪图,我们证明了G中包含至少((δ-4)/(7δ-8))n个点不交的K_4~-.作为推论,每—个阶数n≥28且δ(n/7)等的无爪图至少包含(n-7)-2个点不交的K_4~-.     

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

在文献[3]中介绍了一个新的图类-P3-支配图.这个图类包含所有的拟无爪图,因此也包含所有的无爪图.在本文中,我们证明了每一个点数至少是3的三角形连通的P3-支配图是哈密尔顿的,但有一个例外图K1,1,3.同时,我们也证明了k-连通的(k≥2)的P3-支配图是哈密尔顿的,如果an(G)≤k,但有两个例外图K1,1,3 and K2,3.     

局部连通图的群Z_3-连通性

本文研究了局部连通图的群连通性的问题.利用不断收缩非平凡Z_3-连通子图的方法,在G是3-边连通且局部连通的无爪无沙漏图的情况下,获得了G不是群Z_3-连通的当且仅当G是K_4或W_5.推广了当G是2-边连通且局部3-边连通时,G是群Z_3-连通的这个结果.     

3—连通局部连通无爪图是泛连通图

本文证明了若G是连通、局部连通的无爪图,则G是泛连通图的充要条件为G是3-连通图.这意味着H.J.Broersma和H.J.Veldman猜想成立.     

无爪图中不相邻子图P_4和K_1度和条件下的哈密尔顿连通性

研究子图的度和图的哈密尔顿性的关系,证明图G是一个n阶3-连通无爪图且最小度δ(G)≥4,如果图G中任意两个分别同构于P_4,K_1的不相邻子图H_1,H_2满足d(H_1)+d(H_2)≥n,则图G是哈密尔顿连通.     

K_(1,4)-受限图的最长路

图G中同构于K_(1,p)的子图叫G的p-爪(p≥3).如果G中任意一个p-爪中1度顶点之间边(在G中的边)的数目≥p-2,则称G为K(1,p-)-受限图,它是无爪图(p=3)时的推广.本文证明了:连通的K_(1,4-)受限图G,若|G|≥7,则G有Hamilton路或有长至少为2δ+2的路.     

K1,p-受限图

图G中同构于Ki,p的子图叫G的p-爪(P≥3)．如果G中任意一个p-爪中1度顶点之间边(在G中的边)的数目≥P-2,则称G为K1,p-受限图,它是无爪图的推广．本文证明了连通、局部2-连通的K1,4-受限图是完全圈可扩的．     

无爪图泛圈性的邻域并条件

证明了,若G是一个p-阶3-连通无爪图,p≠10,11,15,并对G中任意两个不相邻的点u和v,满足|N(u)∪N(v)|≥(p-1)/2,则G是泛圈图.     

Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs

A graph is called claw-free if it contains no induced subgraph isomorphic to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least (|V(G)|-2)/3. At the workshop C&C (Novy Smokovec, 1993), Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N (the graph obtained from a triangle by adding three disjoint pendant edges). Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z₁ (the graph obtained from a triangle by adding one pendant edge). Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if each end-vertex of every induced copy of H in G has degree at least |V(G)|/3+1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.     

K1,4-自由的模κ泛圈图

设G是2-连通的K1，4自由图．本文证明了当δ(G)≥κ 1时，G是模κ泛圈图．这一结果肯定了猜想2，继而也肯定了Thomassen猜想在2-连通图中的正确性．     

无K1,r图中的哈密顿圈（英文）

本文借助对图的本质独立集和图的部分平方图的独立集的研究，对于K1,r图中哈密顿圈的存在性给出了八个充分条件。我们将利用T－插点技术对这八个充分条件给出统一的证明，本文的结果从本质上改进了C－Q.Zhang于1988年利用次形条件给出的k-连通无爪图是哈密顿图的次型充分条件，同时。G.Chen和R.H.Schelp在1995年利用次型条件给出的关于k-连通无K1，4图是哈密顿图的充分条件也被我们的结果改进并推广到无K1,r图。     

Hamilton cycles in 6-connected claw-free graphs (Extended abstract)

Thomassen conjectured in 1986 that every 4-connected line graph is hamiltonian. In this paper, we show that 6-connected line graphs are hamiltonian, improving on an analogous result for 7-connected line graphs due to Zhan in 1991. Our result implies that every 6-connected claw-free graph is hamiltonian.     

Hamiltonian connectedness in 3-connected line graphs

We investigate graphs G such that the line graph L(G) is hamiltonian connected if and only if L(G) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of G, then L(G) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if L(G) does not have an hourglass (a graph isomorphic to K₅−E(C₄), where C₄ is an cycle of length 4 in K₅) as an induced subgraph, and if every 3-cut of L(G) is not independent, then L(G) is hamiltonian connected if and only if κ(L(G))≥3, which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306-315] that every 4-connected hourglass free line graph is hamiltonian connected.     

Degree conditions restricted to induced paths for hamiltonicity of claw-heavy graphs

Broersma and Veldman proved that every 2-connected claw-free and P ₆-free graph is hamiltonian. Chen et al. extended this result by proving every 2-connected claw-heavy and P ₆-free graph is hamiltonian. On the other hand, Li et al. constructed a class of 2-connected graphs which are claw-heavy and P ₆-o-heavy but not hamiltonian. In this paper, we further give some Ore-type degree conditions restricting to induced copies of P ₆ of a 2-connected claw-heavy graph that can guarantee the graph to be hamiltonian. This improves some previous related results.     

Traceability in Small Claw-Free Graphs

We prove that a claw-free, 2-connected graph with fewer than 18 vertices is traceable, and we determine all non-traceable, claw-free, 2-connected graphs with exactly 18 vertices and a minimal number of edges. This complements a result of Matthews on Hamiltonian graphs.     

Topological minors in line graphs — A proof of Zha’s conjecture

In 1992, Xiaoya Zha conjectured that the line graph of a 3-connected non-planar graph contains a subdivision of K ₅. In this paper we prove this conjecture. This result is the main ingredient of [4] where a complete characterization of all the 4-connected claw-free graphs not containing a subdivision of K ₅ is obtained.