论文部分内容阅读
设G是一个图，具有顶点集合V(G)和边集合E(G)。设d是一个非负整数，对任意的x∈V.(G)，如果dG(x)=d，则称G是d-正则图。设g和f是定义在V(G)上的两个整数值函数，使对每个x∈V(G)有0≤g(x)≤f(x)。若H是图G的一个支撑子图，满足g(x)≤dH(x)≤f(x)，则称H是图G的(g，f)-因子。特别地，如果图G本身是一个(g，f)-因子，则称G为一个(g，f)-图。设a，b是两个非负整数，若g(x)=a，f(x)=b对每个x∈V(G)成立，则称(g，f)-因子为[a，b]-因子；如果对每个x∈V(G)有g(x)=f(x)，则称(g，f)-因子为f-因子。如果a=b=k，则称这样的[a，b]-因子为k-因子。易见G的一个完美匹配，Hamilton圈、Hamilton路分别是图G的1-因子、2-因子、[1，2]-因子。设F1，F2，…，Ft是图G的(g，f)-因子，且F1，F2，…，Ft的边集构成一个E(G)的划分，则称F1，F2，…，Ft是图G的一个(g，f)-因子分解。设H是图G的含有t条边的子图，F=.{F1，F2，…，Ft}是G的一个(g，f)-因子分解。如果对每个i，1≤i≤t，有｜E(H)∩E(Fi)｜=1，则称F与H正交。
图的因子理论是图论中的一个重要分支。关于因子理论的最早结果中，最基本、最著名的当属1952年Tutte给出的1-因子定理。1970年，Lovász给出一个图有(g，f)-因子的充分必要条件，从而奠定了一般因子存在性研究的基础。从此以后，图的因子问题的研究日益活跃。
人们研究了正则图有正则因子的各种充分条件，但大部分要求图的连通性很高。低连通图的正则因子的研究还没什么结果。对任意给定的正则图G中一条边e，本文第二章给出了正则图G存在正则因子不含边e的割边数条件。
关于正交因子分解，则是最近几年来兴起的因子理论研究的热点之一。1992年，Alspach、Heinrich和刘桂真提出了正交因子分解问题，它在组合设计中有重要应用价值。闫桂英围绕着这一问题做了许多有意义的工作，在H是某些特定子图的情形，得到了一系列结果。其中结果之一如下：设G是一个(mg+k，mf-k)-图，其中对任意的x∈V(G)，g(x)≥1或f(x)≥5是定义在V(G)上的整数值函数，1≤k＜m，则G存在一个子图R对G的任意子图H，｜E(H)｜=K，R有(g，f)-因子分解与H正交。本文第三章修改了上述结果中的条件，得到一结果。
本文的主要结果如下：Theorem2.3.设k是个偶数，G是一个(kr+i)-正则多重图，且不包含kr-3k/2+i+1条割边，i，r满足0≤i＜k，r≥2，则对任意给定的G中一条边e，G有一个k-因子不包含e。
Theorem3.4.设G是一个(0，mf-k)-图，其中对任意的x∈V(G)，f(x)≥k是定义在V(G)上的整数值函数，1≤k＜m，则G有子图R满足对G的任意子图H，｜E(H)｜=k，R有(0，f)-因子分解与H正交。