關(guān)于(g,f)-3-覆蓋圖*

張元收

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

關(guān)于(g,f)-3-覆蓋圖*

張元收

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

設(shè)G是一個圖,用V(G)和E(G)表示頂點集和邊集,并設(shè)g和f是定義在V(G)上的兩個非負整數(shù)值函數(shù)且g

因子;覆蓋圖

本文所考慮的圖均指有限無向簡單圖。設(shè)G是一個圖,分別用V(G)和E(G)表示圖G的頂點集和邊集,用dG(x)表示頂點x在G中的度數(shù)。設(shè)g和f是定義在V(G)上的非負整數(shù)值函數(shù),并且對于任意的x∈V(G)有g(shù)(x)≤f(x)。圖G的一個(g,f)-因子是G的一個支撐子圖F,使對任意的x∈V(G)有g(shù)(x)≤dF(x)≤f(x)。特別地,若圖G本身是一個(g,f)-因子,則稱G是一個(g,f)-圖。設(shè)a,b是兩個非負整數(shù),若對任意的Πx∈V(G)有g(shù)(x)=a,f(x)=b則稱G的一個(g,f)-因子為[a,b]-因子;類似地,稱一個(g,f)-圖為[a,b]-圖。若圖G的每條邊都有一個(g,f)-因子,則稱圖G是一個(g,f)-覆蓋圖;類似地,可定義[a,b]-覆蓋圖。

1 預(yù)備知識

引理1 設(shè)G是一個圖,g和f是定義在V(G)上的兩個整值函數(shù),且g

引理2 設(shè)G是一個圖,g和f是定義在V(G)上的兩個整值函數(shù),且g

定義ε(S,T)如下

2 主要定理及其證明

定理 設(shè)G是一個圖,g和f是定義在V(G)上的兩個整值函數(shù),且1≤g

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

則

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

將(3)代入(2)式得

dG(T)δG(S,T)≥g(T)(-dG-S(T)+6)+dG(T)dG-S(T)+3|S|(dG(T)-g(T))

=dG-S(T)(dG(T)-g(T))+6g(T)+3|S|(dG(T)-g(T))

因為 dG(x)≥g(x)

所以 dG(T)≥g(T)≥|T|≥1又|S|≥3

有dG(T)δG(S,T)≥6 g(T)+9(dG(T)-g(T))=6 dG(T)+3(dG(T)-g(T))≥6 dG(T),

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

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

即將(4)代入(2)式得

dG(T)δG(S,T)≥g(T)(-dG-S(T)+5)+dG(T)dG-S(T)+9(dG(T)-g(T))

=dG-S(T)(dG(T)-g(T))+5g(T)+9(dG(T)-g(T))

≥5dG(T)+4(dG(T)-g(T))≥5dG(T)

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

此時|S|≥2且dG(S)≥eG(S,T)+4=dG(T)-dG-S(T)+4,

即

將(5)代入(2)式得

dG(T)δG(S,T)≥g(T)(-dG-S(T)+4)+dG(T)dG-S(T)+6(dG(T)-g(T))

=dG-S(T)(dG(T)-g(T))+4 g(T)+6(dG(T)-g(T))

≥4dG(T)+2(dG(T)-g(T))≥4dG(T)

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

此時|S|≥2且dG(S)≥eG(S,T)+3=dG(T)-dG-S(T)+3,

即

將(6)代入(2)式得

dG(T)δG(S,T)≥g(T)(-dG-S(T)+3)+dG(T)dG-S(T)+6(dG(T)-g(T))=dG-S(T)(dG(T)-g(T))+3 g(T)+6(dG(T)-g(T))≥3dG(T)+3(dG(T)-g(T))≥3dG(T)

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

此時|S|≥2且dG(S)≥eG(S,T)+2=dG(T)-dG-S(T)+2,

即

將(7)代入(2)式得

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

=dG-S(T)(dG(T)-g(T))+2g(T)+6(dG(T)-g(T))

≥2dG(T)+4(dG(T)-g(T))≥2dG(T)

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

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

dG(S)≥eG(S,T)+1=dG(T)-dG-S(T)+1

即

將(8)代入(2)式得

dG(T)δG(S,T)≥g(T)(-dG-S(T)+1)+dG(T)dG-S(T)+3(dG(T)-g(T))

=dG-S(T)(dG(T)-g(T))+g(T)+3(dG(T)-g(T))

≥dG(T)+2(dG(T)-g(T))≥dG(T)

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

情形7 若上述6種情形都不滿足則有|S|≥0

dG(S)≥eG(S,T)=dG(T)-dG-S(T)

即將(9)代入(2)式得

dG(T)δG(S,T)≥g(T)(-dG-S(T))+dG(T)dG-S(T)=dG-S(T)(dG(T)-g(T))≥0

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

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

當T=Φ時,δG(S,T)=f(S)>2|S|≥ε(S,T)。

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