張新鴻 ,代瀟娜 ,李瑞娟

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

§1 引言

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

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

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

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

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

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

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

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

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

§2 預(yù)備知識(shí)

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

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

(2)V(D)V0是D的一個(gè)頂點(diǎn)覆蓋.

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

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

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

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

情形1|V0|=0

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

情形2|V0|=1

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

如果|V2|≥2,那么

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

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

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

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

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

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

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

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

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

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

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

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

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

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

情形1

設(shè)={z}.由外獨(dú)立雙羅馬控制函數(shù)的定義可知,D中所有賦值為0和賦值為1的頂點(diǎn)均被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的一個(gè)最大獨(dú)立集.

“充分性” 下面分兩種情形進(jìn)行證明.

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

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

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

設(shè)I2是D[N+(z1)∩N+(z2)]的一個(gè)最大獨(dú)立集,則I2也是D的一個(gè)最大獨(dú)立集.注意到z1,z2/∈I2,令h2=易知h2是D的一個(gè)外獨(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 外樹(shù)

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

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

圖2 外樹(shù)

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

證當(dāng)depth()=1時(shí),是一個(gè)有向星圖,因此β()=1,這樣就有

當(dāng)depth(-)≥2時(shí),顯然有n ≥3.下面對(duì)的階n使用數(shù)學(xué)歸納法進(jìn)行證明.

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

情形1至少包含一個(gè)強(qiáng)莖u

設(shè)v是與強(qiáng)莖u相鄰的一個(gè)葉子,外樹(shù)=T{v}.由和的結(jié)構(gòu)以及頂點(diǎn)覆蓋的定義可知,β()=β().進(jìn)一步地,由外獨(dú)立雙羅馬控制數(shù)的定義以及歸納假設(shè)可得

情形2中不存在強(qiáng)莖

設(shè)v是的一個(gè)葉子且λ(v)=depth(),w是v的父節(jié)點(diǎn),x是w的父節(jié)點(diǎn).

子情形2.1d+(x)≥2

因?yàn)棣?v)=depth(-),所以x的所有子節(jié)點(diǎn)只可能是葉子或莖.令=,此時(shí)β()=β()+1.設(shè)f是的一個(gè)γoidR()-函數(shù).定義上的一個(gè)函數(shù)f1使其滿(mǎn)足f1(z)=f(z),其中z ∈V(T′).因?yàn)镹+T(w)=v且f是的一個(gè)γoidR()-函數(shù),所以f1是的一個(gè)外獨(dú)立雙羅馬控制函數(shù).

子情形2.1.1f(x)=3

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

子情形2.1.2f(x)=2

在此情形下,不難知道f(w)+f(v)=3.因?yàn)榈乃星o都不是強(qiáng)莖,所以x最多有一個(gè)葉子x′.

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

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

子情形2.1.3f(x)=1

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

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

(a)d+(x)=2

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

(b)d+(x)≥3

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

子情形2.1.4f(x)=0

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

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

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

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

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

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

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

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

子情形2.2d+(x)=1

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

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

如果f(x)=2,那么f(w)+f(v)=3.又f2是的一個(gè)外獨(dú)立雙羅馬控制函數(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是的一個(gè)外獨(dú)立雙羅馬控制函數(shù),故γoidR()≤ω(f2)=γoidR()-3,因此γoidR()>2β()+1.

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

不難驗(yàn)證,當(dāng)depth()=1,即是一個(gè)有向星圖時(shí),定理4.1的界是緊的.

§5 Nordhaus-Gaddum型不等式

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

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

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

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

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