張?jiān)?/p>

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

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

張?jiān)?/p>

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

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

因子;覆蓋圖

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

1 預(yù)備知識(shí)

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

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

定義ε(S,T)如下

2 主要定理及其證明

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

證明 對(duì)V(G)的所有不交子集S和T,由引理2證明(1)式成立。當(dāng)T≠Φ時(shí),對(duì)任意的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條邊,這時(shí)必有|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))

因?yàn)?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,此時(shí)必有|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。

此時(shí)|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。

此時(shí)|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。

此時(shí)|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此時(shí)|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≠Φ時(shí),證明了δG(S,T)≥ε(S,T)成立。

當(dāng)T=Φ時(shí),δG(S,T)=f(S)>2|S|≥ε(S,T)。

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

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

則G是(g,f)-3-覆蓋圖。

證明 對(duì)Πx,y∈V(G)有g(shù)(x)≤p(x)≤dG(x)≤q(x),且(f(x)-3)dG(y)≥(f(x)-3)p(y)≥(q(x)-3)g(y)≥(dG(x)-3)g(y)

由定理知圖G是(g,f)-3-覆蓋圖。

[1]Lovasz L.Subgraphs with prescribed valencies[J].J Comb Theo ry,1970,8:391-416.

[2]Hoinrich K,Hell P,Kirkpartriok D G,et al.A simple existence criterion for(g

[3]Liu G Z.On(g

[4]Liu G Z.(g

[5]Liu G Z.(g

[6]周思中.關(guān)于(g

On(g

ZHANG Yuan-shou
(Weifang University,Weifang 261061,China)

Let G be a graph with vertex set V(G)and edge set E(G),and let and be two integer-valued functions defined on V(G)such that g

factor,covered graph

O157.5

A

1671-4288(2010)02-0081-04

(責(zé)任編輯:劉乃生)

2009-10-30

張?jiān)?1979-),男,山東壽光人,濰坊學(xué)院數(shù)學(xué)與信息學(xué)院講師。