图的因子和圈

论文摘要

如果图G的一个子图F是G的一个支撑子图，则称F是G的一个因子．Akiyama和Kano将图的因子问题分为两类，分别称为：度因子问题和分支因子问题．如果用因子的度来描述这个因子，则称该因子为度因子．例如，如果一个因子F的所有度都等于1，F是一个1-因子．与此同时，哈密尔顿圈问题可以看成是寻找一个连通的因子使得每个点的度恰好等于2．另一个方面，如果一个因子是用图的概念来描述，则成该因子为分支因子．例如，如果一个因子F的每个分支都是一条路，F为路因子．如果F的每个分支要么是一个圈要么是一条边，F也是一个分支因子，称为完美2-匹配．论文的第一个结果是对路因子覆盖图的刻画．如果图的每条边都在某个路因子上，则称这个图是路因子覆盖的．路因子覆盖图的重要性来源于它是对匹配覆盖图的推广．Akiyama，Avis和Era证明了：图G有一个路因子当且仅当对G的每个点子集S，G去掉S的孤立点的数目都小于等于S的2倍．对长路因子，Kaneko给出了Tutte-类型的刻画：图G有一个路因子使得每条路都至少有3个点当且仅当对G的每个点子集S，G去掉S的太阳分支的数目都小于等于S的2倍．基于这两个结论，我们用收缩边的方式给出了路因子覆盖图的充分必要条件．论文的第二个部分研究了极小2-匹配覆盖图．如果图G的每条边都在G的一个完美2-匹配上，则称图G是一个2-匹配覆盖图．2-匹配覆盖图与可正则化图是等价的．可正则化图的概念是由Berge提出并研究的．并且Berge给出了2-匹配覆盖图的Tutte-类型的刻画．沿着这个方向，我们定义了极小2-匹配覆盖图．一个2-匹配覆盖图G被称为是极小的，如果G去掉任意一条边都不是2-匹配覆盖的．利用相同的技术，我们给出了2-匹配覆盖图的刻画的新的证明．利用这个定理我们证明了：如果一个一个极小2-匹配覆盖图G不同构于K2和K4，则G的最小度为2，并且G不含Kn（n≥5）作为它的子图．其它的性质也相应得到．论文的最后部分致力于研究图的圈方面的问题．我们证明了：对一个顶点数为n的9-连通图，如果σ6（G）≥n+4（α（G）-1），则该图是哈密尔顿的．我们还得到：如果一个n个顶点的（k+2）-连通满足（?）k+3（G）≥n+k（k+2），则该图有一个k-控制圈．用相同的方法，对任意一个连通图，论文给出了一个多项式时间算法要么输出两条不交的路要么输出图的一个结构．我们进一步讲研究方法推广到对边染色完全图Knc的研究．图G的一个圈C称为是交错的，如果C的相邻两条边着有不同的颜色．Bollobas和Erdos在1976年猜想：如果△（Knc）<[n／2]，则Knc包含一个哈密尔顿圈．这里△（Knc）表示和Knc的某个点关联的着有相同颜色的最大边数．受到这个猜想的启发，我们给出了Knc中交错圈长度的下界：如果△（Knc）<[n／2]，则Knc包含一个长度至少为[（n+2）/3]+1的交错圈．

论文目录

• 摘要
• Abstract
• 第一章 引言
• §1.1 基本概念和记号
• §1.2 路因子覆盖图
• §1.3 2-匹配覆盖图
• §1.4 图的路和圈
• 第二章 路因子覆盖图
• §2.1 引言
• ≥2-因子覆盖图'>§2.2 P_≥2-因子覆盖图
• ≥3-因子覆盖图'>§2.3 P_≥3-因子覆盖图
• 第三章 2-匹配覆盖图
• §3.1 引言
• §3.2 2-匹配覆盖图的新的证明
• §3.3 引理
• §3.4 极小2-匹配覆盖图的性质
• 第四章 图的圈和路
• §4.1 引言和记号
• §4.2 9-连通图的哈密尔顿圈
• §4.2.1 引理
• §4.2.2 定理4.1的证明
• §4.3 图的k-控制圈
• §4.4 图的两条不交的路
• §4.4.1 算法
• §4.4.2 定理4.17的证明
• §4.5 边染色完全图的交错圈
• 参考文献
• 在学期间完成的学术论文
• 研究展望
• 致谢