广义轮图的F－控制

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

(华东交通大学 理学院，南昌 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.