论文部分内容阅读
图因子理论是图论的一个重要分支。多年以来,图因子一直是一个比较活跃的研究主题。本文主要研究的是因子的结构理论。因子问题能自然地被划分成两类:度约束因子和分支因子。在1891年,丹麦数学家Peterson首先尝试研究因子问题。在1970年,Lovász研究了(g,f)-因子并且给出了(g,f)-因子的结构理论。他在1972年的文章中进一步研究了更一般的度约束因子:设日是一个集合值函数,当H满足给定性质时,他给出了H-因子存在性的一个充要条件。这个定理推广了各类因子的判据,包括1-因子,k-因子,f-因子,[a,b]-因子,甚至于(g,f)-因子。尽管Lovász给出了这些结果,但是由于证明过程是相当复杂和困难的,因此很少人能理解这些证明及其结果,甚至对于很多因子研究者理解起来都是相当困难的。我们的部分工作是对这些结果给出一些简单的证明,以便以后能有更多的研究者比较容易地理解它们。本研究分为三个部分:
第一部分由第二章组成。首先我们使用交错迹研究了(g,f)-因子结构并且给出了一个结构分解。对于Lovász的因子结构定理,我们给出了一个简单的证明,并且也获得了一些漂亮的结构性质。此外,尽管定义方法不同,但我们证明了我们的分拆与Lovász在1970年给出的分拆是一致的,而且我们的证明也蕴含了这个分拆问题是有多项式算法的。接下来我们定义一种新的迹,叫做可变迹,我们依据这个定义对日-因子定理给出了一个简单而又优雅的证明,并且我们给出了另外一个结构分解。进一步,我们证明了此分拆和Lovász在1972年给出的分拆也是一致的。最后依据我们的结构性质,我们给出了分数f-因子数的计算公式,这是分数匹配数的一个扩展。
第二部分由第三章和第四章组成。在第三章,我们研究分支因子问题。对于这个问题,尽管存在一些刻画,但是太部分情况的刻画仍然没有被发现。在这章我们给出了分支因子的一些刻画,并给出了一些充分条件。在第四章,我们研究特征值和正则因子之间的关系。这方面的研究始于Brouwer和Haemers[15],他们依据Laplacian特征值给出了完美对集的一个充分条件。对正则图,他们依据第三大邻接特征值λ3给出了一个改进。我们所做的工作是:依据第三大邻接特征值λ3,给出了正则图中正则因子存在性的一个充分条件。
第三部分着重研究顶点着色边赋权问题。这个问题和H-因子问题有密切的联系。例如,顶点着色2-边权问题等价于寻找一个特殊的H-因子。我们证明了每个3-连通二部图允许一个顶点着色2-边权。此外,我们还证明了每个4-可着色图允许一个顶点着色4边权。特别地,每个平面图允许一个顶点着色4边权。