图的哈密尔顿性是结构图论的一个重要而且意义深远的研究课题.该问题的产生和发展与著名的四色猜想的研究密切相关，因而备受国内外众多图论专家和学者的关注.图的哈密尔顿路的问题与结构图论中哈密尔顿性的研究也是密切相关的.从算法复杂性来讲，判定一个图是否存在一条哈密尔顿路是NP-完全的.因此，对哈密尔顿路的问题的研究主要集中在给出图中存在哈密尔顿路的充分条件. 关于一个图为哈密尔顿连通图的充分条件主要包含以下两类:一类是从参数的角度刻画，常用的有独立数，度和，最小度，邻域并等;另一类是从结构图论的角度，考虑禁用某些特定的子图.设H是由连通图所组成的图类.若对任意的图H∈H，图G都不包含H作为导出子图，则称图G是H-free的并且称H是图G的一个禁用子图.一个图称为无爪图如果这个图是K1,3-free的.Faudree等人在文献[J.R.Faudree,R.J.Faudree,Z.Ryjá(c)ek and P.Vrána,On forbidden pairsimplying Hamiltion-connectedness，J Graph Theory72(2012)，247-365.]中证明了:对于X=K1，3并且Y∈{P8，N1，1，3，N1，2，2}，如果G是3-连通{X，Y}-free图，则图G是哈密尔顿连通的.在第二章中，我们部分推广了该结果，证明了任何3-连通{K1，3，N1，2，3}-free图都是哈密尔顿连通图. 注意到图G中存在一条哈密尔顿路当且仅当下述三个条件之一成立: (i)图G中存在恰含两个叶子点的支撑树. (ii)图G中存在含零个分枝点的支撑树. (iii)图G中存在最大度至多为2的支撑树. 因此，下述问题是图中哈密尔顿路问题的自然推广. (1)图G中存在至多k个叶子点的支撑树. (2)图G中存在至多k个分枝点的支撑树. (3)图G中存在最大度至多为k的支撑树. 目前，关于图中是否存在上述三类支撑树问题的研究，主要利用的参数包括:独立数，坚韧度，度和，最小度，邻域并等.Matsuda，Ozeki和Yamashita在文献[H.Matsuda,K.Ozeki and T.Yamashita, Spanning trees with a bounded number ofbranch vertices in a claw-free graph, Graphs and Combinatorics.30(2014)429-437.]中证明了:设k是一个非负整数，G是连通无爪图.若α(G)≤2k+2，则G中存在至多k个分枝点的支撑树.在第三章中，我们证明了:设k和r都是整数，其中k≥2和r≥4，G是2-连通K1,r-free图.若α(G)≤k+「k+1/r-3(」)-([)1/r-k-3|+1」，则G中存在至多k个叶子点的支撑树，并且该结论中独立数的上界是最好可能的.由此我们得到如下推论:设k是一个非负整数，G是2-连通K1,4-free图.若α(G)≤2k+5，则G中存在至多k个分枝点的支撑树.此外，我们给出了如下定理:设k是一个非负整数，G是连通K1,4-free图.若α(G)≤2k+5，则图G中存在至多k个分枝点的支撑树或者图G中含有一个块B使得α(B)≤2.最后，我们提出了如下猜想:设k是一个整数，其中k≥2，G是2-连通无爪图.若α(G)≤2k+2，则G中存在至多k个叶子点的支撑树.
展开▼
