馮寶成，高洪秀，岳 軍，李宏升

(青島理工大學(xué) 理學(xué)院，青島 266525)

1 簡(jiǎn)單圖與因子理論

本文考慮的圖G為無(wú)向簡(jiǎn)單圖[1]，設(shè)G=(V(G),E(G))，其中V(G)是頂點(diǎn)集，E(G)是邊集。對(duì)于x∈V(G)，x在G中的度用dG(x)表示。G-S表示去掉S中的點(diǎn)以及和S相關(guān)聯(lián)的邊得到的圖。若F是G的一個(gè)支撐子圖且對(duì)任意x滿足g(x)≤dF(x)≤f(x)，其中g(shù)(x)，f(x)是定義在頂點(diǎn)集上的兩個(gè)整數(shù)值函數(shù)，則F是G的(g,f)-因子，當(dāng)g(x)=a，f(x)=b時(shí)稱F為[a,b]-因子，若a=b=k，則稱F是圖G的一個(gè)k-因子[2]。

對(duì)于圖的研究有許多分支，而因子理論是其中最重要、最熱門的分支之一。圖因子的研究始于丹麥數(shù)學(xué)家PETERSE，19世紀(jì)初他證明了2連通三次圖的1-因子存在性，TUTTLE推廣1-因子定理得出f-因子存在的充要條件，LOVASZ[3]對(duì)頂點(diǎn)度約束條件的研究得到(g,f)-因子，KATERINIS[4]給出圖因子存在的度條件，隨后關(guān)于圖因子的研究結(jié)果大量涌現(xiàn)，如[a,b]-因子，k-因子，1-因子等等。郝國(guó)輝研究了完全三部圖的因子存在性[5]。王璐把無(wú)爪圖和2-因子理論相結(jié)合[6]，得出無(wú)爪圖存在2-因子的一個(gè)條件。在受限圖[7]中可以進(jìn)一步研討因子的存在性條件。

2 主要結(jié)果及其證明

2.1 本文結(jié)果

圖參數(shù)在因子理論研究中有重要意義，尤其頂點(diǎn)度、階數(shù)與圖因子的關(guān)系極其密切，文獻(xiàn)[8]通過對(duì)頂點(diǎn)度和階數(shù)的分析得出圖因子的一個(gè)存在條件，本文進(jìn)一步分析了不相鄰頂點(diǎn)的度和與圖因子的關(guān)系，得到[a,b]-因子存在的又一個(gè)充分條件。

2.2 定理證明

證明結(jié)論需要兩個(gè)已證的引理。

引理1[3]設(shè)0

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

引理2[4]設(shè)0

dG-S(x)≤a-1

證明 當(dāng)a=b=k≥2時(shí)，則結(jié)論成立[2]。以下假設(shè)a

假設(shè)G無(wú)[a，b]-因子， 由引理1知， 存在V(G)的兩個(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≠φ

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

子情況2.1NT[x1]≠T

再設(shè)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)

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

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

(6)

因?yàn)镹T[x1]=T，故t

(7)

定理證畢。

3 結(jié)論

現(xiàn)代因子理論研究主要包括因子的存在性條件、特定性質(zhì)的因子、因子的臨界性以及因子分解4個(gè)方面，而因子存在性的充分條件與圖的階數(shù)和頂點(diǎn)度有很大關(guān)系。本文結(jié)論和文獻(xiàn)[8]都是從這兩個(gè)方面探討因子的存在條件，二者關(guān)于頂點(diǎn)度條件是一致的，而本文對(duì)圖階數(shù)的要求有所改進(jìn)，本文結(jié)論中圖的階數(shù)條件為

文獻(xiàn)[8]中圖的階數(shù)要求滿足