关于(g,f)-3-覆盖图*

张元收

(潍坊学院,山东 潍坊 261061)

关于(g,f)-3-覆盖图*

张元收

(潍坊学院,山东 潍坊 261061)

设G是一个图,用V(G)和E(G)表示顶点集和边集,并设g和f是定义在V(G)上的两个非负整数值函数且g

因子;覆盖图

本文所考虑的图均指有限无向简单图。设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)-图。设a,b是两个非负整数,若对任意的Πx∈V(G)有g(x)=a,f(x)=b则称G的一个(g,f)-因子为[a,b]-因子;类似地,称一个(g,f)-图为[a,b]-图。若图G的每条边都有一个(g,f)-因子,则称图G是一个(g,f)-覆盖图;类似地,可定义[a,b]-覆盖图。

1 预备知识

引理1 设G是一个图,g和f是定义在V(G)上的两个整值函数,且g

引理2 设G是一个图,g和f是定义在V(G)上的两个整值函数,且g

定义ε(S,T)如下

2 主要定理及其证明

定理 设G是一个图,g和f是定义在V(G)上的两个整值函数,且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-覆盖图。定理证毕。

推论 设G是一个(p,q)图,g和f是定义在V(G)上的两个整值函数,且1≤g

则G是(g,f)-3-覆盖图。

证明 对Πx,y∈V(G)有g(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]周思中.关于(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

(责任编辑:刘乃生)

2009-10-30

张元收(1979-),男,山东寿光人,潍坊学院数学与信息学院讲师。