APP下载

广义轮图的F-控制

2015-01-13徐保根张博涵赵丽鑫

宜春学院学报 2015年3期
关键词:奇数偶数广义

徐保根,邹 妍,张博涵,赵丽鑫

(华东交通大学 理学院,南昌 330013)

1 相关定义

本文所讨论的图为无向简单图,文中的符号和术语若无特别说明的,同于文献[1-3]。

近些年来,人们对图的控制理论的研究不断深入,成果也越来越丰富。G.S.Domke、S.T.Hedetniemi及R. C. Laskar 最先提出并研究了图的Fractional 控制,[4]T. W. Haynes 等人综述了图的控制理论的主要研究成果。[5]至今为止,关于图的Fractional 控制的研究成果还比较少,一些特殊图的Fractional 控制数尚未给出。

定义1 设G = V,( )E 为一个图,如果一个实值函数f:V → 0,[ ]1 对任意u ∈V,均有f(N[u])≥1 成立,则称f 为图G 的一个Fractional控制函数(简称为F-控制函数),图G 的Fractional 控制数(简称为F-控制数)定义为γf(G)= min{f(V)| f 为图G 的一个F-控制函数},并称满足γf( )G = f(V)的F-控制数f 为图G 的一个最小F-控制函数。[1]

定义2 设G = V,( )E 为一个图,如果一个实值函数f:V → 0,[ ]1 对任意u ∈V,均有f(N[ ]u )≤1 ,则称f 为图G 的包装函数。[1]

如果图G 的包装函数f 满足:对任意满足f(u)<1 的顶点u ∈V,均存在v ∈N[ ]u ,使得f ( N[ u ])= 1 成立,则称f 为图G 的极大包装函数。

图G 的F-包装数pf(G)和上F-包装数Pf(G)分别定义如下:

min {f(V)| f 为图G的一个极大包装函数 },Pf(G)=

max {f(V)| f 为图G的一个极大包装函数 }。

引理 1 对任意图 G,均有 Pf(G) =γf(G)。[1]

引理2 对任意图G,若f(N[u])= 1 (u∈V)成立,则可推出Pf(G)= γf(G)。

2 主要结果

设W n,( )t 表示有n n ≥( )2 层圈,每个圈上有t t ≥( )4 个点的广义轮图(如图1 所示)。

图1 广义轮图W n,( )t

其中,

证明:令V = V Wn,( )

t ,对广义轮图中的顶点标号,记为y、xi(3 ≤i ≤n ),如图1 所示。定义一个函数f:V → 0,[ ]1 如下:

其中,

首先,对xi关于t 求导数,得到:

判断x'i的 正 负,即 等 同 于 判 断 (-1 )i-1·(ai-1an+1-aian)的正负。

∵an-i+1恒大于0。

当i 为偶数时,(-1 )i-2·an-i+1大于0;当i 为奇数时,(-1)i-2·an-i+1小于0。即对于同一个整数,数列 { x2k}随着t 的增大而增大,数列 { x2k+1}随着t 的增大而减小。

其次,令g( )t = xi,t ≥4 且3 ≤i ≤n。判断xi(3 ≤i ≤n )是否均在0 到1 之间,当i 为偶数时,只需证得且当i 为奇数时,只需证得g( 5 )≤1 且

此外,数列 a{ }n 有此性质:an-1+an+1= 3an。

接下来证明i 为偶数的情况。

(Ⅰ)先证明g( )4 ≥0 。

∵i 为偶数,

因此,

利用数列 a{ }n 的性质,得到:

要判断g( )4 是否大于等于0,由于分母an-1+an大于0,只需要判断分子是否大于0 即可。

经过计算,

因此有g( )4 ≥0 。

而当i 为奇数时,可类似证得0 ≤xi≤1(i =3,4,…n)。

综上所述,对任意的xii = 0,1,…,()n ,均有0 ≤xi≤1 成立。

其中:定理证毕。

[1]徐保根. 图的控制与染色理论[M]. 武汉:华中科技大学出版社,2013.

[2]张先迪,李正良. 图论及其应用[M]. 北京:高等教育出版社,2005.

[3] Bondy JA,Murty VSR.Graph theory with applications[M].New York:Elsevier,1976.

[4] GS Domke,ST Hedetniemi,RC Laskar.Fractional packings,coverings and irredundance in graphs [J].Congr.Numer.,1988,(66):227-238.

[5] TW Haynes,ST Hedetniemi,PJ Slater.Domination in Graphs[M].New York:Marcel Dekker Inc.,1998.

[6]徐保根,赵丽鑫,邹妍. 关于图的Fractional 控制数[J].江西师范大学学报(理科版),2014,38(5):531-533.

猜你喜欢

奇数偶数广义
Rn中的广义逆Bonnesen型不等式
奇数凑20
奇数与偶数
偶数阶张量core逆的性质和应用
关于奇数阶二元子集的分离序列
从广义心肾不交论治慢性心力衰竭
王夫之《说文广义》考订《说文》析论
广义RAMS解读与启迪
有多少个“好数”?
奇偶性 问题