广义轮图的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 且