有向圖的外獨立雙羅馬控制

張新鴻 ,代瀟娜 ,李瑞娟

(1.太原科技大學 應用科學學院,山西太原 030024;2.山西大學 數(shù)學科學學院,山西太原 030006)

§1 引言

本文所采用的術語和符號參見文獻[1]. 如無特別說明, 本文所涉及的圖都是非空的, 有限簡單有向圖. 設D=(V(D),A(D))是一個有向圖, 其中V=V(D)為D的頂點集,A=A(D)為D的弧集.D的頂點數(shù)稱為D的階數(shù). 如果對于任意兩個頂點u,v ∈V(D), 有uv ∈A(D)或者vu ∈A(D)或者uv ∈A(D)和vu ∈A(D), 則稱該有向圖為半完全有向圖. 特別地, 如果對于任意兩個頂點u,v ∈V(D), 有uv ∈A(D)或者vu ∈A(D), 則稱該有向圖為定向圖. 如果uv是D的一條弧, 則稱u是v的一個內(nèi)鄰(或v是u的一個外鄰). 對于頂點v ∈V(D),N-(v) =(v) ={u ∈V -v:uv ∈A(D)}和N+(v) =(v) ={w ∈V -v:vw ∈A(D)}分別稱為v的開內(nèi)鄰集和開外鄰集. 類似地,N-[v] =N-(v)∪{v}和N+[v] =N+(v)∪{v}分別稱為v的閉內(nèi)鄰集和閉外鄰集.d-(v) =(v) =|N-(v)|和d+(v) =(v) =|N+(v)|分別稱為v的內(nèi)度和外度.δ-=δ-(D) = min(v) :v ∈V(D)}和δ+=δ+(D) = min(v) :v ∈V(D)}分別稱為D的最小內(nèi)度和最小外度. 類似地, ?-= ?-(D) = max(v) :v ∈V(D)}和?+= ?+(D) =max(v):v ∈V(D)}分別稱為D的最大內(nèi)度和最大外度.

對于D的一個頂點子集,若其中任意兩個頂點互不相鄰,則稱該頂點子集為D的一個獨立集.獨立集的最大基數(shù)稱為獨立數(shù),記為α(D).設S是D的一個頂點子集,如果N+[S]=V(D),則稱S是D的一個控制集.控制集的最小基數(shù)稱為控制數(shù),記為γ(D).具有最小基數(shù)的控制集稱為γ(D)-集.設Q是D的一個頂點子集,若N+[Q]=V(D)且N+[Q]Q是D的一個獨立集,則稱Q為D的一個頂點覆蓋.頂點覆蓋的最小基數(shù)稱為頂點覆蓋數(shù),記為β(D).具有最小基數(shù)的頂點覆蓋稱為β(D)-集.

1999年,Stewart[2]提出了關于羅馬控制的問題,之后Cockayne[3]等學者進一步定義了羅馬控制函數(shù)并進行了深入的研究[4-6].隨著研究的不斷深入,產(chǎn)生了多種羅馬控制的衍生類型,如雙羅馬控制[7-8],三羅馬控制[9],全羅馬控制[10],符號羅馬控制[11]等.

假設h:V(D)→{0,1,2,3}是定義在D上的一個函數(shù),如果函數(shù)h滿足

(1) 每個賦值為0的頂點至少有兩個賦值為2的內(nèi)鄰或一個賦值為3的內(nèi)鄰;

(2) 每個賦值為1的頂點至少有一個賦值為2或3的內(nèi)鄰;

(3) 所有賦值為0的頂點都是不相鄰的,

則稱函數(shù)h是D的一個外獨立雙羅馬控制函數(shù),記為h=(V0,V1,V2,V3),其中Vi={v ∈V(D) :f(v)=i},i ∈{0,1,2,3}.一個外獨立雙羅馬控制函數(shù)h的權重ω(h)=一個外獨立雙羅馬控制函數(shù)的最小權重稱為外獨立雙羅馬控制數(shù),記為γoidR(D).如果ω(h)=γoidR(D),則稱函數(shù)h是D的一個γoidR(D)-函數(shù).

文獻[12-13]研究了無向圖的外獨立雙羅馬控制.本文將外獨立雙羅馬控制的概念推廣到了有向圖中,研究了有向圖的外獨立雙羅馬控制數(shù)的界,并在此基礎上給出了外樹的外獨立雙羅馬控制數(shù)的下界.同時,進一步刻畫了外獨立雙羅馬控制數(shù)的Nordhaus-Gaddum型不等式.

§2 預備知識

觀察2.1設D是一個有向圖,h=(V0,V1,V2,V3)是D的一個γoidR(D)-函數(shù),則

(1)V2∪V3是D的一個控制集.

(2)V(D)V0是D的一個頂點覆蓋.

引理2.2設D是一個有向圖,則必存在一個γoidR(D)-函數(shù)h=(V0,V1,V2,V3)滿足|V0|0.

證利用反證法.假設h=(V0,V1,V2,V3)是D的任意一個γoidR(D)-函數(shù)且|V0|=0,那么顯然有|V3|=0.進一步地,可以斷言|V1|0.否則,|V2|=|V(D)|,這樣就有ω(h)=2|V2|=2|V(D)|.任取D中一個內(nèi)度不為零的頂點v,定義函數(shù)g:V(D)→{0,1,2,3}使得g(v)=1,g(x)=2,其中x ∈V(D){v}.容易驗證g是D的一個外獨立雙羅馬控制函數(shù),且ω(g)=2|V(D){v}|+1=2|V(D)|-1<2|V(D)|=ω(h),與h是D的一個γoidR(D)-函數(shù)矛盾,故|V1|0.任取頂點w ∈V1,由外獨立雙羅馬控制函數(shù)的定義,w必存在一個賦值為2的內(nèi)鄰,記為z.定義函數(shù)f:V(D)→{0,1,2,3}使得f(w)=0,f(z)=3,f(y)=h(y),其中y ∈V(D){w,z}.不難驗證,f是D的一個γoidR(D)-函數(shù)且|V0|0,矛盾.

引理2.3設D為n階半完全有向圖,那么γoidR(D)≥n+1.

證設h=(V0,V1,V2,V3)是D的一個γoidR(D)-函數(shù).因為D的任意兩個頂點都相鄰,所以由外獨立雙羅馬控制函數(shù)的定義中條件(3)可知|V0|≤1,此時|V1|+|V2|+|V3|≥n-1.下面分兩種情形進行討論.

情形1|V0|=0

此時就有|V2|≥1,那么|V1|+|V2|+|V3|=n,可得

情形2|V0|=1

此時必有|V3|≥1或|V2|≥2.如果|V3|≥1,那么

如果|V2|≥2,那么

當?+(D)=n-1時,引理2.3的界是緊的(參看圖1(b)).

圖1 (a):一個7階有向星圖S,設f是S的一個γoidR(S)-函數(shù),令f(v0)=3,f(vi)=0,i ∈{1,··· ,6},則γoidR(S)=3.(b):一個6階完全有向圖D,設g是D的一個γoidR(D)-函數(shù),令g(v0)=3,g(v1)=0,g(vi)=1,i ∈{2,··· ,5},則γoidR(D)=7

§3 外獨立雙羅馬控制數(shù)的界

命題3.1設D是一個n階有向圖,則γoidR(D)≥δ-(D)+2.

證設h=(V0,V1,V2,V3)是D的一個γoidR(D)-函數(shù).如果|V0|=0,那么|V3|=0,進一步有γoidR(D)≥n+1≥δ-(D)+2.如果|V0|0,那么任取頂點x ∈V0.由外獨立雙羅馬控制函數(shù)的定義可知,有N-(x)?V1∪V2∪V3.又x在V3中至少有一個內(nèi)鄰點或在V2中至少有兩個內(nèi)鄰點,故|V2|≥2或|V3|≥1,這樣就有

在有向星圖和完全有向圖上,命題3.1的界是緊的(參看圖1).

命題3.2設D是一個n階有向圖,則γoidR(D)≤n+γ(D).

證設S是D的一個γ(D)-集,易知h=(V0,V1,V2,V3)=(?,VS,S,?)是D的一個外獨立雙羅馬控制函數(shù),那么γoidR(D)≤ω(h)=2|S|+|VS|=n+|S|=n+γ(D).

引理3.3設D是一個n階有向圖,則β(D)+2≤γoidR(D)≤3β(D).

證設Q是D的一個β(D)-集.由β(D)-集的定義知h=是D的一個外獨立雙羅馬控制函數(shù),因此γoidR(D)≤3|Q|=3β(D).

定理3.4設D是一個n ≥2階的有向圖且δ-(D)≥1,則γoidR(D)=β(D)+2 當且僅當下列條件之一成立.

(1) 存在一個頂點z ∈V(D)滿足d+(z)=n-1.

(2) 存在兩個頂點z1,z2使得V(D)=N+[z1]∪N+[z2],并且D[N+(z1)∩N+(z2)]的每一個最大獨立集也是D的一個最大獨立集.

證“必要性” 由引理2.2,設是D的一個γoidR(D)-函數(shù)且滿足0.又由γoidR(D)=β(D)+2以及引理3.3中的(2)式,可得這樣,就有1且下面分兩種情形進行討論.

情形1

設={z}.由外獨立雙羅馬控制函數(shù)的定義可知,D中所有賦值為0和賦值為1的頂點均被z控制,因此d+(z)=n-1.

β(D)≤|V(D)I1|<|V(D)I|=|V(D)()|+2=+2=γoidR(D)-2,與β(D)=γoidR(D)-2矛盾.因此,I是D的一個最大獨立集.

“充分性” 下面分兩種情形進行證明.

情形1存在一個頂點z ∈V(D)滿足d+(z)=n-1

若D中的任意兩個頂點都相鄰,則β(D)=n-1.由引理2.3可知,γoidR(D)=n+1=β(D)+2.否則,D中至少存在兩個頂點互不相鄰.設I1是D的一個最大獨立集,由d+(z)=n-1可知,z/∈I1.因此,令易知h1是D的一個外獨立雙羅馬控制函數(shù).這樣就有γoidR(D)≤ω(h1)=n-α(D)-1+3=n-α(D)+2=β(D)+2,又由引理3.3可知γoidR(D)=β(D)+2.

情形2存在兩個頂點z1,z2使得V(D)=N+[z1]∪N+[z2],并且D[N+(z1)∩N+(z2)]的每一個最大獨立集也是D的一個最大獨立集

設I2是D[N+(z1)∩N+(z2)]的一個最大獨立集,則I2也是D的一個最大獨立集.注意到z1,z2/∈I2,令h2=易知h2是D的一個外獨立雙羅馬控制函數(shù).由δ-(D)≥1,有β(D)=|V(D)I2|.因此γoidR(D)≤ω(h2)=|V(D)I2| -2+4=|V(D)I2|+2=β(D)+2,又由引理3.3,就有γoidR(D)=β(D)+2.

§4 外樹

本節(jié)刻畫外樹的外獨立雙羅馬控制數(shù)的下界.

設T是一棵有向樹,如果存在一個頂點r ∈V(T),使得d-(r)=0,且對任意的頂點v ∈V(T){r}都有d-(v)=1,則稱T是一棵以r為根的外樹,記為.若d+(v)=0,則稱v為的一個葉子,與v相鄰的頂點稱為的一個莖.如果一個莖至少相鄰兩個葉子,則稱為的一個強莖.對于頂點,若d+(w)/=0,則稱w為的一個分支點.設w是的一個分支點,若從頂點w到頂點v有一條弧wv,則稱v為w的一個子節(jié)點(或稱w為v的一個父節(jié)點).注意到,在任意的一棵外樹中,從根r到任意一個頂點有且僅有一條路,故記λ(v)是從根r到頂點v的路長,則depth()=max{λ(v)稱為外樹的深度.特別地,當depth()=1時,稱為一個有向星圖.圖2是一棵以r為根的外樹,v1,v2是兩個葉子,w是一個與v1,v2相鄰的強莖,x是w的父節(jié)點(或w是x的子節(jié)點),x是v1的一個祖先(或v1是x的一個子孫),depth()=4.

圖2 外樹

定理4.1設是一棵n ≥2階的外樹,則γoidR()≥2β()+1.

證當depth()=1時,是一個有向星圖,因此β()=1,這樣就有

當depth(-)≥2時,顯然有n ≥3.下面對的階n使用數(shù)學歸納法進行證明.

n=3時,易知γoidR()=5=2β()+1.設對于階為k ≤n -1的任意樹,都有γoidR()≥2β()+1.接下來分兩種情形進行討論.

情形1至少包含一個強莖u

設v是與強莖u相鄰的一個葉子,外樹=T{v}.由和的結構以及頂點覆蓋的定義可知,β()=β().進一步地,由外獨立雙羅馬控制數(shù)的定義以及歸納假設可得

情形2中不存在強莖

設v是的一個葉子且λ(v)=depth(),w是v的父節(jié)點,x是w的父節(jié)點.

子情形2.1d+(x)≥2

因為λ(v)=depth(-),所以x的所有子節(jié)點只可能是葉子或莖.令=,此時β()=β()+1.設f是的一個γoidR()-函數(shù).定義上的一個函數(shù)f1使其滿足f1(z)=f(z),其中z ∈V(T′).因為N+T(w)=v且f是的一個γoidR()-函數(shù),所以f1是的一個外獨立雙羅馬控制函數(shù).

子情形2.1.1f(x)=3

由f是的一個γoidR()-函數(shù)易知,f(w)=0,f(v)=2.又f1是的一個外獨立雙羅馬控制函數(shù),故γoidR()≤ω(f1)=γoidR()-2,這樣就有γoidR()≥γoidR()+2≥2β()+3=2β()+1.

子情形2.1.2f(x)=2

在此情形下,不難知道f(w)+f(v)=3.因為的所有莖都不是強莖,所以x最多有一個葉子x′.

若x的所有子節(jié)點中有唯一的一個葉子x′,則f(x′)=1.令g是上的一個函數(shù)且滿足(g(x′),g(x),g(w),g(v))=(0,3,0,2),g(y)=f(y),其中y ∈V(){x′,x,w,v}.易知g是的一個外獨立雙羅馬控制函數(shù),且ω(g)=γoidR()-1<ω(f),矛盾.

若x的所有子節(jié)點都是莖.設w1是x的一個不同于w的子節(jié)點,是w1的子節(jié)點.由λ(v)=depth()可知是一個葉子,則f(w1)+f()=3.令g1是上的函數(shù)且滿足g1(x),g1(w),g1(v))=(2,0,3,0,2),g1(y)=f(y),其中y容易知道g1是的一個外獨立雙羅馬控制函數(shù),且ω(g1)=γoidR()-1<ω(f),矛盾.

子情形2.1.3f(x)=1

類似地,有f(w)+f(v)=3.因為f(x)=1,所以depth()≥3.否則,x為的根,這就意味著x將無法得到其它頂點的支援,從而與外獨立雙羅馬控制函數(shù)的定義矛盾.

若x的所有子節(jié)點中有唯一的一個葉子x′,那么f(x′)=2.定義上的一個函數(shù)h滿足(h(x′),h(x),h(w),h(v))=(0,3,0,2),h(y)=f(y),其中y ∈V(){x′,x,w,v},可以驗證函數(shù)h是的一個外獨立雙羅馬控制函數(shù),且ω(h)=γoidR()-1<ω(f),矛盾.因此,x的所有子節(jié)點都是莖.進一步地,考慮下面兩種情形.

(a)d+(x)=2

設w1是x的一個不同于w的子節(jié)點,是w1的一個子節(jié)點,這樣就有f(w1)+f()=3.由f1是的一個外獨立雙羅馬控制函數(shù)且γoidR()≤ω(f1)=γoidR()-3可知

(b)d+(x)≥3

在此情形下必存在x的兩個不同于w的子節(jié)點w1和w2,設分別是w1,w2的子節(jié)點,同理有類似地,定義上的一個函數(shù)h1滿足其中y可知h1是的一個外獨立雙羅馬控制函數(shù),且ω(h1)=γoidR(T)-1<ω(f),矛盾.

子情形2.1.4f(x)=0

與子情形2.1.3類似,此時f(w)+f(v)=3且depth()≥3.

斷言x的子節(jié)點情況只能為以下三種情形之一.(a)x的子節(jié)點中除w外還包含一個葉子;(b)x的所有子節(jié)點都是莖且d+(x)=2;(c)x的所有子節(jié)點都是莖且d+(x)=3.

證如若不然,則或者x的子節(jié)點中既有葉子,又至少有一個不同于w的莖;或者x的所有子節(jié)點都是莖且d+(x)≥4.

若x的子節(jié)點中既有葉子,又至少有一個不同于w的莖,那么設w1是不同于w的一個莖,是w1的子節(jié)點.這樣就有f(x′)=2,f(w1)+f()=3.定義上的一個函數(shù)l滿足

則l1是的一個外獨立雙羅馬控制函數(shù),且ω(l1)=γoidR(T)-1<ω(f),矛盾.下面證明當情形(a-c)成立時,定理的結論成立.

若(a)成立,則由f(x)=0可知,f(x′)=2.因為f1是的一個外獨立雙羅馬控制函數(shù),所以γoidR()≤ω(f′)=γoidR()-3.又γoidR()≥2β(T′)+1且β(T)=β(T′)+1,故γoidR()>2β()+1.

若(b)成立,則設w1是x的一個不同于w的子節(jié)點,w′1是w1的子節(jié)點,這樣就有f(w1) +f()=3.又f1是的一個外獨立雙羅馬控制函數(shù)且γoidR()≤ω(f1)=γoidR()-3,故γoidR()>2β()+1.

若(c)成立,則必存在x的兩個不同于w的子節(jié)點,記為w1和w2.設,分別是w1和w2的子節(jié)點,則f(w1)+f()=3,f(w2)+f()=3.由f1是的一個外獨立雙羅馬控制函數(shù)且γoidR()≤ω(f1)=γoidR()-3可知,γoidR()>2β()+1.

子情形2.2d+(x)=1

設=,此時β()=β()+1.設f是的一個γoidR()-函數(shù),定義上的一個函數(shù)f2使其滿足f2(z)=f(z),其中z ∈V(T′).與子情形2.1類似,f2是的一個外獨立雙羅馬控制函數(shù).

如果f(x)=3,那么f(w)+f(v)=2.又f2是的一個外獨立雙羅馬控制函數(shù),故γoidR()≤ω(f2)=γoidR()-2,這樣γoidR()≥2β()+1.

如果f(x)=2,那么f(w)+f(v)=3.又f2是的一個外獨立雙羅馬控制函數(shù),故γoidR()≤ω(f2)=γoidR()-3,這樣γoidR()>2β()+1.

如果f(x)=0或f(x)=1,那么f(w) +f(v)=3.由子情形2.1.3和2.1.4的證明可知,depth()≥3.又f2是的一個外獨立雙羅馬控制函數(shù),故γoidR()≤ω(f2)=γoidR()-3,因此γoidR()>2β()+1.

綜上所述,若是一棵n ≥2階的外樹,則γoidR()≥2β()+1.

不難驗證,當depth()=1,即是一個有向星圖時,定理4.1的界是緊的.

§5 Nordhaus-Gaddum型不等式

定理5.1設D是一個n ≥2階的有向圖,則γoidR(D)+γoidR(D)≥n+3.

由圖3可知,定理5.1的界是緊的.

圖3 (a)一個n階有向圖D:設h是D的一個γoidR(D)-函數(shù),令h(v0)=3, h(vi)=0,i ∈{1,···,n -1},則γoidR(D)=3;(b)D的補圖: 設h1是的一個γoidR()-函數(shù),令h1(v1)=3,h1(v0)=h1(v2)=0, h1(vi)=1,i ∈{3,···,n-1},則γoidR()=n

圖4 (a)一個5階有向星圖S: 設g是S的一個γoidR(S)-函數(shù),令g(v0)=3,g(vi)=0,i ∈{1,2,3,4},則γoidR(S)=3;(b) S的補圖: 設g1是的一個γoidR()-函數(shù),令g1(v0)=0, g1(v1)=3, g1(vi)=1, i ∈{2,3,4},則γoidR()=6

定理5.2設D是一個n ≥2階的定向圖,則γoidR(D)+γoidR()≥n+4.