关于图的分数因子的若干结果

论文摘要

图的因子理论是图论的一个重要分支，在图论研究中得到了极大关注。在日常生活中，许多诸如编码设计、积木设计，计算机网络传输、进度表等关于运筹和网络设计问题都涉及到图的因子，因子分解和正交因子[15]。其中，文件传输问题可以模拟为因子和（0，f）-因子分解（或f-染色），拉丁方块和空间方块的设计则涉及到图的因子和正交因子问题。本文所考虑的图都是有限简单图。设G是一个图，V（G）是顶点集，E（G）是边集，x在图G中的度记为dG（x）。λ（G）和κ（G）分别表示图G的边连通度和连同度。δ（G）表示G的最小度。如果S是V（G）的子集，G|S|由S导出的子图。GS的孤立节点的集合是I（GS）并且|I（GS）|=i（GS）。对于V（G）两个不联通的子集S，T，EG（S，T）表示一个顶点属于S另一个顶点属于T的边集，并且|EG（S，T）|=eG（S，T）。令g和f是两个整数值函数对所有x∈V（G）满足0≤g（x）≤f（x）。G的一个（g，f）-因子F是G的一个生成子图，满足对于所有的x∈V．（C），有g（x）≤dF（x）≤f（x）。一个分数（g，f）-示性函数是一个函数h，h为G的每条边分配一个在[0，1]中的数，因此对于任意x∈V（G）我们有g（x）≤dGh≤f（x），其中dGh（x）=∑e∈Exh（e）是x∈V（G）的分子度，并且Ex={e：e=xy∈E（G）}。令h是图G的一个分数（g，f）-示性函数，令Eh={e：e∈E（G）且h（e）≠0}。如果Gh是G的生成子图满足E（Gh）=Eh，则Gh成为G的分数（g，f）-因子。如果对于所有x∈V（G），g（x）=f（x）=k（k是一个非负整数），这个分数（g，f）-因子称为分数k-因子。尤其，分数l-因子也称为分数完美匹配。令G=（V（G），E（G））是一个图，并令g和f是两个定义在V（G）上的整数值函数且对所有的x∈V（G）有g（x）≤f（x）成立。若对G的每一条边e都存在G的一个分数（g，f）-因子Gh使得h（e）=0，其中h是Gh的示性函数，则称G是一个分数（g，f）-消去图。若在G中删去E′（?） E（G），|E′|=k后，所得图有分数完美匹配，则称G是分数k-边-可消去的。G被称为分数（g，f）-覆盖图，如果G的每一条e，都存在一个分数（g，f）-因子Gh，使得h（e）=1，其中h是Gh的示性函数。一个简单图G是分数k-可扩的，如果每一个分数k-匹配M都可以被扩展成分数完美匹配Gh，并且对于所有的e∈M，有h（e）=1。G是分数k-因子-临界的，如果删去任意k-个顶点，剩下的子图仍有分数完美匹配。图G是分数k-覆盖的，如果G的每一条边e都属于一个分数k-因子Gh，且满足h（e）=1，其中h是Gh的示性函数。一个图是分数k-可扩的，如果每一个k-匹配M可以被扩展成一个分数完美匹配Gh，满足对于所有的e∈M，都有h（e）=1。本文分为六章主要从三个方面研究了分数图，并得到了一些结果。首先论文讨论了消去图，研究了图是1-可消去，2-可消去和k-边-可消去的与韧度和孤立韧度相关的充分条件，并证明了这些结果在一定意义上是最好可能的。其次研究了分数可覆盖图，给出了一个图是分数1-覆盖，2-覆盖的关于韧度和孤立韧度的充分条件，并证明了这些结果在某些意上是最好可能的。还给出了一个（g，f）-因子覆盖一个k-匹配的充分必要条件。此外，还研究了可扩和临界图，证明了关于分数k-可扩的若干充分条件。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景和问题的提出
• 1.2 论文研究内容
• 1.3 论文组织结构
• 第二章 图的因子与分数因子研究的若干进展
• 2.1 基本结果
• 2.2 图的分数可消去性
• 2.3 图的分数可覆盖性
• 2.4 图的分数可扩性及因子临界性
• 第三章 关于分数可消去图
• 3.1 定义与基本引理
• 3.2 主要结果和证明
• 第四章 分数覆盖图
• 4.1 定义与基本引理
• 4.2 主要结果和证明
• 第五章 分数k-可扩图和因子临界图
• 5.1 定义与基本引理
• 5.2 图的分数k-可扩性
• 5.3 图的强分数k-可扩性
• 5.4 图的分数因子临界性
• 第六章 结束语
• 参考文献
• 在校期间发表的学术论文
• 致谢