关于(g,f)-3-消去图*

2011-02-02 00:57:24张元收
潍坊学院学报 2011年2期
关键词:定义

张元收

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

1 引言

本文所考虑的图均指有限无向简单图。设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的任何一条边e,G都有一个(g,f)-因子不含e,则称图 G是一个(g,f)-消去图;类似地,可定义[a,b]-消去图。

2 预备引理

引理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)如下

3 主要定理及其证明

定理 设G是一个图,g和f是定义在V(G)上的两个整值函数,且 g<f-1,若对任意的 x,y∈V (G),有 f(x)≤dG(x)且 f(x)(dG(y)-3)≥dG(x)g(y),则 G是(g,f)-3-消去图。

注意到 dG(S)-dG(T)≥-dG-S(T),所以

情形1 若G[T]中至少有3条边,这时必有|T|≥3,且

将(4)代入(2)式得

因为 dG(x)≥g(x),所以 dG(S)≥f(S)≥3|S|≥3

所以 δG(S,T)≥6

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

将(4)代入(2)式得

所以 δG(S,T)≥5

此时|T|≥2且

dG(T)≥eG(S,T)+4=dG(T)-dG-S(T)+4 即

将(5)代入(2)式得

所以 δG(S,T)≥4

情形4 若上述3种情况都不满足,且 G[T]中只有1条边,且eG(T,V(G)(S∪T))=1;或 G[T]中没有边,且eG(T,V(G)(S∪T))≥3

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

将(6)代入(2)式得

所以 δG(S,T)≥3

情形5 若上述4种情况都不满足,且 G[T]中只有1条边,且eG(T,V(G)(S∪T))=0;或G[T]中没有边,且eG(T,V(G)(S∪T))=2

此时|T|≥2且

将(7)代入(2)式得

所以 δG(S,T)≥2

情形6 若上述5种情况都不满足,且 G[T]中没有边,且eG(T,V(G)(S∪T))=1;此时|T|≥1且

将(8)代入(2)式得

所以 δG(S,T)≥1

情形7 若上述6种情形都不成立。此时dG-S(T)≥0,又dG(s)≥f(S),于是δG(S,T)≥0。这样在S≠Φ时证明了δG(S,T)≥ε(S,T)成立。

当 S=Φ时,有δG(S,T)=dG(T)-g(T)≥3|T|≥ε(S,T)

登录APP查看全文

猜你喜欢
定义
活用定义巧解统计概率解答题
例谈椭圆的定义及其应用
题在书外 根在书中——圆锥曲线第三定义在教材和高考中的渗透
永远不要用“起点”定义自己
海峡姐妹(2020年9期)2021-01-04 01:35:44
严昊:不定义终点 一直在路上
华人时刊(2020年13期)2020-09-25 08:21:32
定义“风格”
成功的定义
山东青年(2016年1期)2016-02-28 14:25:25
有壹手——重新定义快修连锁
修辞学的重大定义
当代修辞学(2014年3期)2014-01-21 02:30:44
山的定义
公务员文萃(2013年5期)2013-03-11 16:08:37