廣義輪圖的F－控制

徐保根，鄒 妍，張博涵，趙麗鑫

(華東交通大學(xué) 理學(xué)院，南昌 330013)

1 相關(guān)定義

本文所討論的圖為無向簡(jiǎn)單圖，文中的符號(hào)和術(shù)語(yǔ)若無特別說明的，同于文獻(xiàn)［1－3］。

近些年來，人們對(duì)圖的控制理論的研究不斷深入，成果也越來越豐富。G.S.Domke、S.T.Hedetniemi及R. C. Laskar 最先提出并研究了圖的Fractional 控制，［4］T. W. Haynes 等人綜述了圖的控制理論的主要研究成果。［5］至今為止，關(guān)于圖的Fractional 控制的研究成果還比較少，一些特殊圖的Fractional 控制數(shù)尚未給出。

定義1 設(shè)G = V，( )E 為一個(gè)圖，如果一個(gè)實(shí)值函數(shù)f:V → 0，[ ]1 對(duì)任意u ∈V，均有f(N［u］)≥1 成立，則稱f 為圖G 的一個(gè)Fractional控制函數(shù)(簡(jiǎn)稱為F－控制函數(shù))，圖G 的Fractional 控制數(shù)(簡(jiǎn)稱為F－控制數(shù))定義為γf(G)= min{f(V)| f 為圖G 的一個(gè)F－控制函數(shù)}，并稱滿足γf( )G = f(V)的F－控制數(shù)f 為圖G 的一個(gè)最小F－控制函數(shù)。［1］

定義2 設(shè)G = V，( )E 為一個(gè)圖，如果一個(gè)實(shí)值函數(shù)f:V → 0，[ ]1 對(duì)任意u ∈V，均有f(N[ ]u )≤1 ，則稱f 為圖G 的包裝函數(shù)。［1］

如果圖G 的包裝函數(shù)f 滿足:對(duì)任意滿足f(u)＜1 的頂點(diǎn)u ∈V，均存在v ∈N[ ]u ，使得f ( N[ u ])= 1 成立，則稱f 為圖G 的極大包裝函數(shù)。

圖G 的F－包裝數(shù)pf(G)和上F－包裝數(shù)Pf(G)分別定義如下:

min {f(V)| f 為圖G的一個(gè)極大包裝函數(shù) }，Pf(G)=

max {f(V)| f 為圖G的一個(gè)極大包裝函數(shù) }。

引理 1 對(duì)任意圖 G，均有 Pf(G) =γf(G)。［1］

引理2 對(duì)任意圖G，若f(N［u］)= 1 (u∈V)成立，則可推出Pf(G)= γf(G)。

2 主要結(jié)果

設(shè)W n，( )t 表示有n n ≥( )2 層圈，每個(gè)圈上有t t ≥( )4 個(gè)點(diǎn)的廣義輪圖(如圖1 所示)。

圖1 廣義輪圖W n，( )t

其中，

證明:令V = V Wn，( )

t ，對(duì)廣義輪圖中的頂點(diǎn)標(biāo)號(hào)，記為y、xi(3 ≤i ≤n )，如圖1 所示。定義一個(gè)函數(shù)f:V → 0，[ ]1 如下:

其中，

首先，對(duì)xi關(guān)于t 求導(dǎo)數(shù)，得到:

判斷x'i的 正 負(fù)，即 等 同 于 判 斷 (－1 )i－1·(ai－1an+1－aian)的正負(fù)。

∵an－i+1恒大于0。

當(dāng)i 為偶數(shù)時(shí)，(－1 )i－2·an－i+1大于0;當(dāng)i 為奇數(shù)時(shí)，(－1)i－2·an－i+1小于0。即對(duì)于同一個(gè)整數(shù)，數(shù)列 { x2k}隨著t 的增大而增大，數(shù)列 { x2k+1}隨著t 的增大而減小。

其次，令g( )t = xi，t ≥4 且3 ≤i ≤n。判斷xi(3 ≤i ≤n )是否均在0 到1 之間，當(dāng)i 為偶數(shù)時(shí)，只需證得且當(dāng)i 為奇數(shù)時(shí)，只需證得g( 5 )≤1 且

此外，數(shù)列 a{ }n 有此性質(zhì):an－1+an+1= 3an。

接下來證明i 為偶數(shù)的情況。

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

∵i 為偶數(shù)，

因此，

利用數(shù)列 a{ }n 的性質(zhì)，得到:

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

經(jīng)過計(jì)算，

因此有g(shù)( )4 ≥0 。

而當(dāng)i 為奇數(shù)時(shí)，可類似證得0 ≤xi≤1(i =3，4，…n)。

綜上所述，對(duì)任意的xii = 0，1，…，()n ，均有0 ≤xi≤1 成立。

其中:定理證畢。

［1］徐保根. 圖的控制與染色理論［M］. 武漢:華中科技大學(xué)出版社，2013.

［2］張先迪，李正良. 圖論及其應(yīng)用［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］徐保根，趙麗鑫，鄒妍. 關(guān)于圖的Fractional 控制數(shù)［J］.江西師范大學(xué)學(xué)報(bào)(理科版)，2014，38(5):531－533.