關(guān)于樹(shù)圖中全控制數(shù)與全外部連通控制數(shù)比值的研究?

莊蔚

(廈門理工學(xué)院應(yīng)用數(shù)學(xué)學(xué)院，福建廈門361024)

0 引言

令G= (V,E)是一個(gè)沒(méi)有孤立點(diǎn)的簡(jiǎn)單圖,v是G中的一個(gè)點(diǎn)．v的開(kāi)鄰域N(v) = {u∈V|uv∈E}，閉鄰域N[v]=N(v)∪{v}．點(diǎn)v的度數(shù)d(v)=|N(v)|．對(duì)于連通圖G中的兩個(gè)點(diǎn)u和v, 它們之間的距離d(u,v)是G中最短(u,v)-路的長(zhǎng)度．G的直徑diam(G)=max{d(u,v)|u,v∈V(G)}．我們將G中度為1的點(diǎn)稱為葉子，與葉子相鄰的點(diǎn)稱為G的支撐點(diǎn)．連到至少兩個(gè)葉子的支撐點(diǎn)稱為強(qiáng)支撐點(diǎn)．將一個(gè)非平凡星（點(diǎn)數(shù)至少為2）的每條邊都剖分一次，稱這個(gè)圖為分割星．

全控制是最重要的控制參數(shù)之一．在一個(gè)不含孤立點(diǎn)的圖G中，若存在一個(gè)點(diǎn)集S，使得N(S)=V(G)，則稱S是G中的一個(gè)全控制集．G的全控制數(shù)γt(G)=min{|S|:S是G中的全控制集}．一個(gè)基數(shù)為γt(G)的全控制集稱為γt(G)-集．與全控制相關(guān)的結(jié)果可參見(jiàn)文獻(xiàn)[1]. 近些年，人們提出了許多新的控制參數(shù)，其中一些參數(shù)與全控制數(shù)密切相關(guān)．在本文中，我們主要研究其中的一種控制參數(shù)，全外部連通控制數(shù)，這種參數(shù)可以看做是全控制數(shù)的一種變形．

Cyman在2010年首先提出全外部連通控制數(shù)的概念[2]，并做了相關(guān)的研究．令D是圖G的一個(gè)全控制集，若點(diǎn)集V(G)D的導(dǎo)出子圖是連通的，則稱D是G的一個(gè)全外部連通控制集．G的全外部連通控制數(shù)γtc(G)=min{|D|:D是G中的全外部連通控制集}．一個(gè)基數(shù)為γtc(G)的全外部連通控制集稱為γtc(G)-集．顯然的，γt(G)≤γtc(G)．

在本文中，我們證明了對(duì)于沒(méi)有強(qiáng)支撐點(diǎn)的樹(shù)T，總是有．另外，我們也刻畫(huà)了能夠使上式等號(hào)成立的圖類．

1 樹(shù)圖中全控制數(shù)與全外部連通控制數(shù)的比值問(wèn)題

在本節(jié)中，我們的目標(biāo)是研究樹(shù)圖中全控制數(shù)與全外部連通控制數(shù)的比值問(wèn)題．根據(jù)全控制數(shù)與全外部連通控制數(shù)的概念，我們有下面的結(jié)論．

觀察1[3]令G是一個(gè)連通圖，且不是一個(gè)星圖，那么在G中必然存在一個(gè)不含葉子的γt-集．

命題1[4]令D是一個(gè)連通圖G的γtc-集，|G|≥3，最小度δ(G)=1．那么D包含了G的所有支撐點(diǎn)．進(jìn)一步的，如果γtc(G)≤n?2，那么D也包含G中的所有葉子．

定理1令T是一個(gè)非平凡樹(shù)，則

另一方面，給定任意的樹(shù)T, 然后構(gòu)造一系列的樹(shù)圖T0(=T),T1,T2,···，其中Ti+1是在Ti的基礎(chǔ)上，通過(guò)增加一個(gè)點(diǎn)，并把這個(gè)點(diǎn)連到Ti的一個(gè)支撐點(diǎn)上得到的，i=0,1,2,···．通過(guò)觀察1，在構(gòu)造這些樹(shù)圖的過(guò)程中，每個(gè)Ti的全控制數(shù)都保持不變，但通過(guò)性質(zhì)1和全外部連通控制數(shù)的定義，隨著下標(biāo)i的增大，每個(gè)Ti的全外部連通控制數(shù)一直都在增加．這意味著當(dāng)n足夠大時(shí)，會(huì)不斷趨近于無(wú)窮大．所以在下文中，我們主要討論不含強(qiáng)支撐點(diǎn)的樹(shù)圖．

下面，我們定義樹(shù)T的點(diǎn)標(biāo)記這個(gè)概念(這種點(diǎn)標(biāo)記的方式在[6]中被首次提出)．首先對(duì)V(T)劃分成三個(gè)點(diǎn)集S=(SA,SB,SC)，若一個(gè)點(diǎn)v∈Sx(x∈{A,B,C})，則說(shuō)明v被字母x所標(biāo)記．我們也可以說(shuō)v的狀態(tài)是x，或記為sta(v)=x．我們把(T,S)稱為T的標(biāo)記樹(shù)．

令U 是這樣一族標(biāo)記樹(shù):

(i) 包含(P4,S0)，其中S0是在P4的基礎(chǔ)上，給P4的兩個(gè)葉子分配狀態(tài)C，兩個(gè)支撐點(diǎn)分配狀態(tài)A;

(ii) 對(duì)于操作P1是封閉的（操作P1的說(shuō)明如下）．

操作P1: 取某個(gè)(T′,S′)∈U，令v是(T′,S′)中一個(gè)狀態(tài)為A的點(diǎn)．另取一條4-路v1v2v3v4和一個(gè)點(diǎn)u，分別連接u,v2兩點(diǎn)和u,v兩點(diǎn)．令sta(v1)=sta(v4)=C, sta(v2)=sta(v3)=A，sta(u)=B．（如圖1所示）

圖1 操作P1

令(T,S) ∈U 是一個(gè)標(biāo)記樹(shù)．那么必然存在一系列的標(biāo)記樹(shù)(P4,S0), (T1,S1),···,(Tk?1,Sk?1), (Tk,Sk)使得(Tk,Sk)=(T,S)，其中每個(gè)(Ti,Si)都是在(Ti?1,Si?1)的基礎(chǔ)上通過(guò)操作P1獲得．

接下來(lái)，我們先給出一些顯然的結(jié)論．

觀察2令T是一個(gè)點(diǎn)數(shù)不少于4的樹(shù)，S是T的某種標(biāo)記方式使得(T,S)∈U ．則T有下列性質(zhì):

(a) 一個(gè)點(diǎn)的狀態(tài)是A當(dāng)且僅當(dāng)它是支撐點(diǎn)；

(b) 一個(gè)點(diǎn)的狀態(tài)是C當(dāng)且僅當(dāng)它是葉子；

(c)SB∪SC是T的一個(gè)獨(dú)立集, 且

(d)SA是T中唯一的γt-集；

(e) 取任意x∈SB∪SC，則V(T){x}是T的一個(gè)γtc-集．

根據(jù)觀察2 (c)，2 (d) 和2 (e)，可以直接導(dǎo)出下面的引理．

推論1令T是一個(gè)非平凡樹(shù)，S是T的某一種標(biāo)記使得(T,S)∈U ．則

定理2令T是一個(gè)不包含強(qiáng)支撐點(diǎn)的非平凡樹(shù)，則有，上式等號(hào)成立當(dāng)且僅當(dāng)存在某種標(biāo)記S，使得(T,S)∈U ．

證明我們對(duì)樹(shù)T的點(diǎn)數(shù)n來(lái)做歸納法(如前所述，我們只需要考慮沒(méi)有強(qiáng)支撐點(diǎn)的樹(shù))．當(dāng)n≤4時(shí)，結(jié)論顯然成立．令n≥5，假設(shè)對(duì)于任意點(diǎn)數(shù)小于|T|的樹(shù)T′，都有，該式等號(hào)成立當(dāng)且僅當(dāng)存在某種標(biāo)記S′使得(T′,S′)∈U.

當(dāng)diam(T)≤3，結(jié)論顯然成立．進(jìn)一步的，如果，則(T,S)=(P4,S0)∈U ．因此我們假設(shè)diam(T)≥4，令P=v1v2···vt是T的所有最長(zhǎng)路中d(v3)最大的那條最長(zhǎng)路．我們知道d(v2)=2．令D是T中一個(gè)不含葉子的γt-集，則v2,v3∈D．若(N(v3){v2})∩D/=?，則令T′=T?{v1,v2}，令R是T′的一個(gè)γtc-集，我們有γtc(T′)+2 ≥γtc(T)，γt(T)?1 ≥γt(T′)．這意味著因此我們考慮(N(v3){v2})∩D=?的情況．

聲明1d(v3)=2.

如果d(v3)>2，那么d(v3) = 3，且v3是T的一個(gè)支撐點(diǎn)．假設(shè)d(v4)>2,u1是v4在P外的一個(gè)鄰點(diǎn)．那么在T?u1v4中，包含u1的那個(gè)分支T1，要么是一個(gè)3-路u1u2u3，要么是一個(gè)4-路uu1u2u3(其余的每一種情況，要么類似于我們上面已經(jīng)討論的情況，要么與條件(N(v3){v2})∩D=?相矛盾)．在任一種情況中，令T′是T?v4u1里包含v4的那個(gè)分支．則有γtc(T′)+4 ≥γtc(T)，γt(T)?2 ≥γt(T′)．這意味著

因此，d(v4)=2．于是令T′和T′′分別是T?v4v5中包含v5和v4的分支，我們有γtc(T′)+5 ≥γtc(T)，γt(T)?2 ≥γt(T′)．這意味著．如果γtc(T) =．上面的不等式等號(hào)都成立．特別的，有根

據(jù)歸納，存在某個(gè)標(biāo)記S′，使(T′,S′)∈U ．若v5在S′中有狀態(tài)B或C，那么根據(jù)觀察2(e)，R′=V(T′){v5}是T′的一個(gè)γtc-集，于是R′∪(V(T′′){v4})是T的一個(gè)全外部連通控制集．即γtc(T′)+4 ≥γtc(T)，矛盾．因此v5在S′中有狀態(tài)A．令S是在S′的基礎(chǔ)上通過(guò)將v1和v3的葉鄰點(diǎn)(leaf-neighbor)標(biāo)記為C，v2和v3標(biāo)記為A，v4標(biāo)記為B而獲得的．那么(T,S)可以在(T′,S′)的基礎(chǔ)上通過(guò)操作P1而被獲得．因此(T,S)∈U ．

通過(guò)聲明1，我們有d(v3)=2．若d(v4)≥3，令u是v4在P外的一個(gè)鄰點(diǎn)，由于(N(v3){v2})∩D=?和P的選擇方式，T?uv4中那個(gè)包含u的分支是一個(gè)P3，其中u是這個(gè)P3的一個(gè)葉子．當(dāng)d(v4)≥3，令T′=T?{v1,v2,v3}；當(dāng)d(v4)=2，令T′=T?{v1,v2,v3,v4}．類似于上面的討論，我們總是有