莊蔚

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

0 引言

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

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

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

在本文中，我們證明了對于沒有強支撐點的樹T，總是有．另外，我們也刻畫了能夠使上式等號成立的圖類．

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

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

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

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

定理1令T是一個非平凡樹，則

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

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

令U 是這樣一族標記樹:

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

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

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

圖1 操作P1

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

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

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

(a) 一個點的狀態(tài)是A當且僅當它是支撐點；

(b) 一個點的狀態(tài)是C當且僅當它是葉子；

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

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

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

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

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

定理2令T是一個不包含強支撐點的非平凡樹，則有，上式等號成立當且僅當存在某種標記S，使得(T,S)∈U ．

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

當diam(T)≤3，結(jié)論顯然成立．進一步的，如果，則(T,S)=(P4,S0)∈U ．因此我們假設(shè)diam(T)≥4，令P=v1v2···vt是T的所有最長路中d(v3)最大的那條最長路．我們知道d(v2)=2．令D是T中一個不含葉子的γt-集，則v2,v3∈D．若(N(v3){v2})∩D/=?，則令T′=T?{v1,v2}，令R是T′的一個γ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的一個支撐點．假設(shè)d(v4)>2,u1是v4在P外的一個鄰點．那么在T?u1v4中，包含u1的那個分支T1，要么是一個3-路u1u2u3，要么是一個4-路uu1u2u3(其余的每一種情況，要么類似于我們上面已經(jīng)討論的情況，要么與條件(N(v3){v2})∩D=?相矛盾)．在任一種情況中，令T′是T?v4u1里包含v4的那個分支．則有γ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) =．上面的不等式等號都成立．特別的，有根

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

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