基于度参数的[a，b]-因子存在的一个充分条件

冯宝成，高洪秀，岳 军，李宏升

(青岛理工大学 理学院，青岛 266525)

1 简单图与因子理论

本文考虑的图G为无向简单图[1]，设G=(V(G),E(G))，其中V(G)是顶点集，E(G)是边集。对于x∈V(G)，x在G中的度用dG(x)表示。G-S表示去掉S中的点以及和S相关联的边得到的图。若F是G的一个支撑子图且对任意x满足g(x)≤dF(x)≤f(x)，其中g(x)，f(x)是定义在顶点集上的两个整数值函数，则F是G的(g,f)-因子，当g(x)=a，f(x)=b时称F为[a,b]-因子，若a=b=k，则称F是图G的一个k-因子[2]。

对于图的研究有许多分支，而因子理论是其中最重要、最热门的分支之一。图因子的研究始于丹麦数学家PETERSE，19世纪初他证明了2连通三次图的1-因子存在性，TUTTLE推广1-因子定理得出f-因子存在的充要条件，LOVASZ[3]对顶点度约束条件的研究得到(g,f)-因子，KATERINIS[4]给出图因子存在的度条件，随后关于图因子的研究结果大量涌现，如[a,b]-因子，k-因子，1-因子等等。郝国辉研究了完全三部图的因子存在性[5]。王璐把无爪图和2-因子理论相结合[6]，得出无爪图存在2-因子的一个条件。在受限图[7]中可以进一步研讨因子的存在性条件。

2 主要结果及其证明

2.1 本文结果

图参数在因子理论研究中有重要意义，尤其顶点度、阶数与图因子的关系极其密切，文献[8]通过对顶点度和阶数的分析得出图因子的一个存在条件，本文进一步分析了不相邻顶点的度和与图因子的关系，得到[a,b]-因子存在的又一个充分条件。

2.2 定理证明

证明结论需要两个已证的引理。

引理1[3]设0

其中，s=|S|;t=|T|。

引理2[4]设0

dG-S(x)≤a-1

证明 当a=b=k≥2时，则结论成立[2]。以下假设a

假设G无[a，b]-因子， 由引理1知， 存在V(G)的两个不相交子集S,T使θ(S,T)<0成立，

(1)

且T是使θ(S,T)<0的极小子集。由引理2知，

dG-S(x)≤a-1,∀x∈T

(2)

情况1T=φ