论文摘要
本文考虑的图若无特殊声明均为简单、无向有限图，对于一个图G=G（V（G），E（G）），我们用V（G）和E（G）分别表示图的顶点集合和边集合。对任意的υ∈V（G），我们用dG（υ）表示顶点υ在G中的度数。△（G）和δ（G）分别表示图G的最大度和最小度，在不引起混淆的情况下简记为△和δ。对于图G，我们用|G|=|V（G）|表示G的阶数，即G的顶点数，并定义图G中两个不相邻的顶点的最小度和为：（若G是一个完全图，则令σ2（G）=∞）。对于二部图G，令G的两个部分的顶点集合分别为V1和V2。若|V1|=|V2|,则称G为均衡二部图。定义(若G是一个完全二部图，则令σ1.1=∞)。图的一个路因子就是指每一个分支都是一条路的一个生成子图。给定一个正整数κ，P≥κ-因子就是指每个分支都至少含κ个顶点的一个路因子。对于图G中的一条路P和一个圈C，定义路和圈的长度分别为：l（P）=|V（P）|-1，l（C）=|V（C）|。G的一个哈密顿圈是G的包含G中所有顶点的一个圈。G的一个1-因子是G的一个1-正则支撑子图，通常我们称1-因子为完美对集或完美匹配。显然G的一个1-因子是覆盖G的所有顶点的一个边集合。G的一个2-因子是G的一个2-正则支撑子图，易见2-因子的每一个连通分支为一个圈。图的κ个独立圈是指G中κ个顶点不相交的圈。图的独立圈、2-因子和路因子问题是图的因子理论中非常重要的一部分，也是图的哈密顿圈理论的推广和延伸。它是图论中非常有趣的一类问题，也是国内外研究的热门课题。其理论研究日益成熟和完善，而且它在计算机科学、通信网络设计等中都有重要应用。关于图的独立圈、2-因子和路因子理论的研究主要集中在以下几个方面：图中含指定个数的独立圈和2-因子；含指定长度的独立圈和2-因子；图中具有指定性质的独立圈和2-因子；具有指定性质的路因子等等。全文共分四章。第一章简单介绍了图论的基本概念，圈和路因子理论的历史和发展状况及一些已有的相关结论。这一章是第二章和第三章的基础。第二章讨论了含4k个顶点的简单图的结构和度条件的部分结果。其主要结果如下：定理2．1．1．设G是一个有4k个顶点的简单图，其中k是一个正整数，如果σ2（G）≥4k-2，则G包含k-1个点不相交的4-圈Ci=1，2，...,k-1，并且e(〈G-V(∪i=1k-1Ci)〉)≥2。本文第三章中我们考虑了含6k个顶点的二部图的结构和度条件，提出了用6-圈与12-圈去划分二部图，还有用6-圈去划分二部图。主要证明了如下几个结论。定理3．1．1．设k≥2是一个正整数，G是有6κ个顶点的均衡二部图，|V1|=|V2|=3k，δ1,1（G）≥4k-1，则G包含k-1个点不相交的6-圈。定理3．1．2．设G是有6k（k≥5）个顶点的均衡二部图，|V1|=|V2|=3k，δ1,1（G）≥4k-1，则G可以划分为k-2个6-圈和一个12-圈，并且这k-1圈点不相交。定理3．2．1．设G为二部图，|V1|=|V2|=3k，δ1,1（G）≥4k+1，则G包含k个6-圈。本文第四章主要给出了关于满足一定度条件的图不含指定点的独立圈问题的注释。另外，本文的第二章和第三章最后还提出了一些问题，以待进一步研究。
论文目录
相关论文文献
- [1].用独立圈对图的一个划分[J]. 数学的实践与认识 2010(20)
- [2].二部图中含指定顶点的独立4-圈[J]. 山东大学学报(理学版) 2008(05)
- [3].图中具有指定性质的独立4-圈[J]. 河南师范大学学报(自然科学版) 2010(05)