图中参数与树型结构研究

发布时间：2022-01-16 05:22

　　图的支撑树特征问题一直是结论图论研究中的一个重要课题。该问题的产生与发展都与结构图论中的经典问题一一哈密尔顿问题有着密切联系。众所周知图G中含哈密尔顿路当且仅当G中含至多两个叶子点的支撑树。一个自然的问题是:对于任意的整数k ≥ 2,在何条件下G中存在至多k个叶子点的支撑树?目前国内外对满足一定条件的支撑树存在性问题的研究主要是从参数的角度,如坚韧度、独立数、连通度、度和等方面进行刻画,或者限制在某些特殊的图类中。本文主要研究了禁用子图中的支撑树问题,给出了满足一定条件的支撑树存在的充分条件。全文共分为五章,主要内容如下:在第一章,我们给出文中出现的一些基本概念和符号,介绍了本文的研究背景、研究意义以及国内外在这方面的研究情况。通过对本文研究背景及研究现状的讨论,说明了本文主要研究工作的必要性和创新性。在第二章,我们研究了 K1,5-free图中存在至多5个叶子点的支撑树的充分条件。Kyaw在文献[30]中给出了在连通K1,4-free图中存在至多k个叶子点的支撑树的充分条件,结论如下:设G是连通K1,4-free图,则下述结论成立:（1）如果σ3（G）≥|G|,则G有一条哈密尔顿路.... 

【文章来源】：华中师范大学湖北省 211工程院校 教育部直属院校

【文章页数】：97 页

【学位级别】：博士

【部分图文】：

图１：说明度和下界是最好可能的例子：ｍ?＝?３??

壯学位论文??ＤＯＣＴＯＲＡＩ．ＤＩＳＳＩ?ＲＩＡＴＩＯＮ??第三章ｉ＾ｙｆｒｅｅ图中存在叶子数至多为６的支撑树的??一个充分条件??３．１引言??本章我们研宄／ｖ＼５－ｆｒｅｅ图中至多含６个叶子点的支撑树的存在性，即问题??１．３．１中的子情形／ｃ?＝?６，证明了?／（６）存在且其最大值为２，得至ＩＪ?了以下结论，ＳＰ定理??１．３．３，相关结果在?“Ｍａｔｈｅｍａｔｉｃａｌ?Ｐｒｏｂｌｅｍｓ?ｉｎ?Ｅｎｇｉｎｅｅｒｉｎｇ”?上发表。??设Ｇ是连通ｉ＾－ｆｒｅｅ图．如果ａ７（Ｇ）?＞?｜Ｇ｜?－?２，则Ｇ中包含至多６个叶子点??的支撑树且度和条件的下界是紧的．??本章涉及到的概念与记号与第二章相同。我们昏先用一个例子说明此论断的??条件是紧的。令ｍ是一个正整数，构造图Ｇ如下：设Ｘ是顶点集为的??完全图，（＾，（７２，．．．，（７７是７个点不交的完全图且对任意的《￡［１，７］，（＾￥欠？．将〇：??与的每个点连起来，ｙ和＜７３，（７４的每个点连起来，２和Ｃ７５，Ｃ７６，Ｃ７的每个点??连起来（见图８）．由Ｇ的构造我们容易得出ａ７（Ｇ）?＝?｜Ｇ｜?－?３，但图Ｇ的任一棵支撑??树至少有７个叶子点，因此，定理１．３．３中度和条件的下界是最好可能的。??Ｃ３?Ｃ４?Ｃ５??图８：说明度和下界是最好可能的例子：ｍ?＝?３??３５??

图９：?７！二仿，…，％｝??．．．＇—

【参考文献】：
期刊论文
[1]On a Spanning K-tree Containing Specified Vertices in a Graph[J]. Fei-fei SONG,Zhi-quan HU.  Acta Mathematicae Applicatae Sinica. 2019(04)



本文编号：3592018