基于度參數的[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=φ

由引理1知，S≠φ，又T=φ，故t=0,dG-S(T)=0，

bs-at+dG-S(T)=bs>0

與式(1)矛盾。

情況2T≠φ

設h1=min{dG-S(x)∶x∈T}，且令x1∈T使dG-S(x1)=h1。

子情況2.1NT[x1]≠T

再設h2=min{dG-S(x)∶x∈T-NT[x1]}，且令x2∈T-NT[x1]使dG-S(x2)=h2。

(3)

再令p=|NT[x1]，t≥p+1,p≤h1+1。由式(1)和式(3)得

-1≥bs-at+dG-S(T)≥

bs-at+h1p+h2(t-p)≥

(h1-h2)(h1+1)+h2(p+1)+bs-a(n-s)≥

則

(4)

故式(4)成立。

子情況2.2NT[x1]=T

由式(1)得

-1≥bs-at+dG-S(T)≥bs-at+h1t

(5)

由頂點度條件b≤δ(G)≤dG(x1)≤h1+s,所以s≥b-h1。將s≥b-h1代入式(5)得

b(b-h1)+(h1-a)t+1≤0

(6)

因為NT[x1]=T，故t

(7)

定理證畢。

3 結論

現代因子理論研究主要包括因子的存在性條件、特定性質的因子、因子的臨界性以及因子分解4個方面，而因子存在性的充分條件與圖的階數和頂點度有很大關系。本文結論和文獻[8]都是從這兩個方面探討因子的存在條件，二者關于頂點度條件是一致的，而本文對圖階數的要求有所改進，本文結論中圖的階數條件為

文獻[8]中圖的階數要求滿足