關于消去圖的一個充分條件＊

宋 強

(濰坊學院,山東 濰坊 261061)

0 引言

本文所考慮的圖均指有限無向簡單圖。設G是一個圖,分別用V(G)和 E(G)表示圖G的頂點集和邊集,用 dG(x)表示頂點 x在G中的度數。設 g和f是定義在V(G)上的非負整值函數,并且對于任意的 x∈V(G)有 g(x)≤f(x)。圖G的一個(g,f)-因子是 G的一個支撐子圖 F,使對任意的 x∈V(G),有 g (x)≤dF(x)≤f(x)。

特別地,若圖G本身是一個(g,f)-因子,則稱G是一個(g,f)-圖。如果去掉圖 G的任何三條邊都有一個(g,f)-因子,則稱圖 G是一個(g,f)-3-消去圖。

1 預備引理

引理1 設 G是一個圖,g和f是定義在V(G)上的兩個整值函數,且 g＜f,若對任意的 x,y∈V(G),且 x≠y,有 f(x)dG(y)≥dG(x)g(y),則 G有(g,f)-因子。

引理2 設 G是一個圖,g和f是定義在V(G)上的兩個整值函數,且 g＜f,則圖 G是一個(g,f)-3 -消去圖,當且僅當對V(G)的所有不交子集S和T有

其中ε(S,T)定義如下

2 主要定理及其證明

定理 設G是一個圖,g和f是定義在V(G)上的兩個整值函數,且1≤g＜f-1,若對任意的 x,y∈V (G),有 f(x)≤dG(x)且 f(x)(dG(y)-3)≥dG(x)g(y),則 G是(g,f)-3-消去圖。

證明 對V(G)的所有不交子集S和T,由引理2證明(1)式成立。當S≠?時,由假設,對任意的x,y∈V(G)有 f(x)(dG(y)-3)≥dG(x)g(y),因此

這樣

即

情形1 若G[T]中至少有3條邊,這時必有|T|≥3,且

即 dG-S(T)≥6,于是

情形2 若 G[T]中只有2條邊,且eG(T,V(G)(S∪T))≥1,此時必有|T|≥3且

即 dG-S(T)≥5,于是

dG(S)δG(S,T)≥5(dG(S)-f(S))+9 f(S)≥5 dG(S),所以δG(S,T)≥5。

此時|T|≥2且

即 dG-S(T)≥4,于是

所以δG(S,T)≥4。

此時|T|≥2,且

即 dG-S(T)≥3,于是

所以δG(S,T)≥3。

此時|T|≥2,且

即 dG-S(T)≥2,于是

dG(S)δG(S,T)≥2(dG(S)-f(S))+6 f(S)≥2 dG(S)

所以δg(S,T)≥2。

情形6 若上述5種情況都不滿足,且 G[T]中沒有邊,且eG(T,V(G)(S∪T))=1

此時|T|≥1,且

即 dG-S(T)≥1,于是

所以δG(S,T)≥1。

情形7 若上述6種情形都不滿足,此時|T|≥0,且

即 dG-S(T)≥0,于是

所以δG(S,T)≥0。這樣,在S≠?時證明了δG(S,T)≥ε(S,T)成立。

當S≠?時,δG(S,T)=dG(T)-g(T)≥2|T|≥ε(S,T)。

綜上所述,對V(G)的所有不交子集S和 T,證明了(1)式成立,從而由引理知圖G是(g,f)-3-消去圖。定理證畢。

[1]Lovasz L.Subgraphs w ith p rescribed valencies[J].Comb Theory,1970,8(2):391-416.

[2]Hoinrich K,Hell P,Kirkpartriok D G,et al.A simp le existence criterion for(g＜f)-factors[J].Discrete Mathematics, 1990,85(1):315-317.

[3]Liu G Z.On(g,f)-covered graphs[J].Acta Math Scientia,1988,8(2):181-184.

[4]Liu G Z.(g＜f)-facto rsof graphs[J].Acta Math Scientia,1994,14(3):285-290.

[5]Liu G Z.(g,f)-factors and(g,f)-factorizationsof graphs[J].Acta Math Scientia,1994,37(2):230-236.

[6]周思中.關于(g,f)-2-覆蓋圖和(g,f)-2-消去圖[J].蘭州大學學報:自然科學版,2005,41(6):106-109.