论文部分内容阅读
几十年来,图的支撑树特征问题一直是结构图论中一个重要的研究课题.该问题的产生和发展与结构图论中哈密尔顿问题的研究密切相关,因此受到国内外许多图论专家的关注.若图中存在一条哈密尔顿路,即说明图中存在恰好两个叶子的支撑树或是最大度等于2,即没有分支点的支撑树.自然就有如下问题:能否给出保证图中存在至多k个叶子的支撑树,或是图中存在有限个分支点的支撑树,或是图中存在最大度不超过k的支撑树等一系列问题的条件.同时,若图为哈密尔顿连通图,即说明图中存在以任意两点作为叶子集的支撑树,自然我们就可以试图探求在何种条件下,图中存在以任意k个点作为叶子集的支撑树,由此引出k-叶子连通图的判定问题.众所周知,判定一个图是否含一条哈密尔顿路从算法复杂性来讲是NP-完全的,从而对上述一系列有关保证图中是否存在具有相应特征的支撑树问题也是NP-完全的,于是对于这些问题的研究主要集中在给出相应的充分条件.目前在图中是否存在具有和哈密尔顿性相关的特征的支撑树问题的研究中主要从参数的角度进行刻画,运用坚韧度、独立数、连通度、领域并、度和等条件,集中讨论图中是否存在以下五类特征的支撑树的充分条件:1.图中存在最大度不超过k的支撑树;2.图中存在至多k个分支点的支撑树;3.给定连通度条件下,图中,特别地,K1,r-free图中存在至多k个叶子的支撑树;4.图中存在以任意k个点作为叶子集的支撑树;5.图中存在满足去掉所有叶子后,最大度至多为k的支撑树.本文主要研究了在满足一定连通度条件下,K1,4-free图和K1,5-free图中存在至多有限个叶子的支撑树的度和条件.首先考虑连通K1,4-free图,Kyaw证明了若图G是阶数为n的连通K1,4-free图,(i)若σ3(G)≥n,则G中含一条哈密尔顿路,即恰含两个叶子的支撑树;(ⅱ)当k≥3时,若σ’k+1(G)≥n一k/2,则G中存在至多k个叶子的支撑树.并且说明了结论中的界均为最好可能的.本文提高连通度,考虑m-连通K1,4-free图.证明了图G是阶数为n的m-连通K1,4-free图,其中m≥2,若O’m+3(G)≥n+2m-2,则G中存在至多3个叶子的支撑树.另一方面,本文也研究了连通K1,5-free图中类似的问题,证明了图G为连通K1,5-free图且阶数n≥77,若σ5(G)≥n-1,则G中存在至多4个叶子的支撑树.并且说明了该结论中度和的下界n-1是最好可能的.