有向圖的Roman k-控制

張曉轉(zhuǎn), 孟 巍

(山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006)

設(shè)S是有向圖D的頂點(diǎn)集V的一個(gè)子集,如果N+[S]=V,則稱S是有向圖D的一個(gè)控制集[1].有向圖D中最小控制集的階稱為D的控制數(shù),記作γ(D)[1].設(shè)k是一個(gè)正整數(shù),S是有向圖D中V的一個(gè)頂點(diǎn)子集,如果|N-(v)∩S|≥k對(duì)于每個(gè)v∈VS均成立,則稱S是有向圖D中的一個(gè)k-控制集.有向圖D中最小k-控制集的階稱為k-控制數(shù),記作γk(D).有向圖D中的一個(gè)階數(shù)最小的k-控制集叫做γk(D)-集.有向圖D中的一個(gè)階數(shù)最小的1-控制集叫做γ(D)-集.

圖的控制參數(shù)是圖的一個(gè)重要參數(shù),它與染色體,劃分?jǐn)?shù)等其他參數(shù)有著密切的聯(lián)系,并且它與組合優(yōu)化,理論計(jì)算機(jī)科學(xué)等其他學(xué)科領(lǐng)域都有著密切的聯(lián)系.基于不同的實(shí)際背景,圖論研究者在圖的控制理論的基礎(chǔ)上定義了許多圖的控制參數(shù),比如圖的符號(hào)控制,圖的k-距離控制,圖的Roman控制等.2004年,Cockayne[2]等給出了無(wú)向圖的Roman控制函數(shù)的定義及其相關(guān)結(jié)論.后來(lái),Lutz[1]將它推廣到了有向圖中,給出了有向圖的Roman控制函數(shù).稱函數(shù)f:V→{0,1,2}為有向圖D的一個(gè)Roman控制函數(shù),如果對(duì)于每個(gè)f(v)=0的頂點(diǎn)v都至少有一個(gè)入鄰點(diǎn)w滿足f(w)=2.Roman控制函數(shù)f權(quán)值是指在函數(shù)f作用下各個(gè)頂點(diǎn)的值的和,即ω(f)=∑v∈Vf(v).有向圖D的權(quán)值最小的Roman控制函數(shù)的權(quán)值稱作有向圖D的Roman控制數(shù),記作γR(D).如果函數(shù)f是Roman控制函數(shù)并且ω(f)=γR(D),則稱f是γR(D)-函數(shù).

Kammerling和Volkmann[3]推廣了無(wú)向圖的Roman控制函數(shù),得到了無(wú)向圖的羅馬Romank-控制函數(shù)并且給出了關(guān)于無(wú)向圖的Romank-控制函數(shù)的大量結(jié)果.設(shè)k是一個(gè)正整數(shù),稱函數(shù)f:V→{0,1,2}是無(wú)向圖G的一個(gè)Romank-控制函數(shù),如果對(duì)于每個(gè)f(v)=0的頂點(diǎn)v都至少有k個(gè)鄰點(diǎn)v1,v2,…,vk滿足f(v1)=f(v2)=…=f(vk)=2.文中將這個(gè)函數(shù)推廣到有向圖中,對(duì)有向圖的Romank-控制函數(shù)進(jìn)行了定義和研究.設(shè)k是一個(gè)正整數(shù),稱函數(shù)f:V→{0,1,2}是有向圖D的一個(gè)Romank-控制函數(shù),如果對(duì)于每個(gè)f(v)=0的頂點(diǎn)v它都至少有k個(gè)入鄰點(diǎn)v1,v2,…,vk滿足f(v1)=f(v2)=…f(vk)=2.Romank-控制函數(shù)f的權(quán)值是在函數(shù)f作用下各個(gè)頂點(diǎn)的值的和,即ω(f)=∑v∈Vf(v).有向圖D的權(quán)值最小的Romank-控制函數(shù)的權(quán)值稱作是有向圖D的Romank-控制數(shù),記作γ{Rk}(D).顯然,γ{Rk}(D)≤|V(D)|.如果函數(shù)f是D的Romank-控制函數(shù)且ω(f)=γ{Rk}(D),則稱f是γ{Rk}(D)-函數(shù).注意到Roman 1-控制數(shù)是Roman控制數(shù).

設(shè)f是有向圖D的一個(gè)Romank-控制函數(shù),則f與V的有序劃分(V0,V1,V2)是一一對(duì)應(yīng)的,其中Vi={v∈V|f(v)=i},i=0,1,2.因此,以后可以記f=(V0,V1,V2).

Kammerling和Volkmann在文獻(xiàn)[3]中給出了無(wú)向圖的Roman k-控制數(shù)的一些性質(zhì).我們對(duì)這些性質(zhì)進(jìn)行了推廣,首先給出了有向圖中Roman k-控制數(shù)的一些性質(zhì),然后給出了一些特殊有向圖的Roman k-控制數(shù)的界.

1 Roman k-控制數(shù)的一些性質(zhì)

稱有向圖D是一個(gè)k-Roman有向圖,如果γ{Rk}(D)=2γk(D).設(shè)S是有向圖D的頂點(diǎn)集V的一個(gè)子集,稱頂點(diǎn)v∈S關(guān)于集合S有一個(gè)副出鄰點(diǎn)w,如果w∈N+(v)∩(VS)且N-(v)∩S={w}.

命題1γk(D)≤γ{Rk}(D)≤2γk(D).

證明設(shè)f=(V0,V1,V2)是有向圖D的一個(gè)γ{Rk}(D)-函數(shù),則V1∪V2是D的一個(gè)k-控制集,從而γk(D)≤|V1|+|V2|≤|V1|+2|V2|=γ{Rk}(D).

設(shè)S是有向圖D的一個(gè)γk(D)-集,則f=(VS,?,S)是D的一個(gè)Romank-控制函數(shù),因此γ{Rk}(D)≤2|S|≤2γk(D),證畢.

推論[1]γ(D)≤γR(D)≤2γ(D).

命題2一個(gè)有向圖D是k-Roman有向圖當(dāng)且僅當(dāng)它有一個(gè)γ{Rk}(D)-函數(shù)f=(V0,V1,V2)滿足V1=?.

證明如果D是k-Roman有向圖,設(shè)S是有向圖D的一個(gè)γk(D)-集,則f=(VS,?,S)是D的一個(gè)Romank-控制函數(shù)且ω(f)=2|S|=2γk(D)=γ{Rk}(D).所以D有一個(gè)γ{Rk}(D)-函數(shù)f=(V0,V1,V2)滿足V1=?.

反之,如果D有一個(gè)γ{Rk}(D)-函數(shù)f=(V0,V1,V2)滿足V1=?,那么γ{Rk}(D)=2|V2|,并且|V2|是D的一個(gè)k-控制集.因此2γk(D)≤2|V2|=γ{Rk}(D).結(jié)合命題1得γ{Rk}(D)=2γk(D),因此D是k-Roman羅馬有向圖,證畢.

推論[1]一個(gè)有向圖D是1-Roman有向圖當(dāng)且僅當(dāng)它有一個(gè)γR(D)-函數(shù)f=(V0,V1,V2)滿足V1=?.

命題3設(shè)D是一個(gè)n階有向圖,則以下3條等價(jià):

1)γk(D)=γ{Rk}(D);

2)γk(D)=n;

3) Δ-(D)≤k-1.

證明首先由1)證2).設(shè)f=(V0,V1,V2)是有向圖D的一個(gè)γ{Rk}(D)-函數(shù),由于γ{Rk}(D)=γk(D)≤|V1|+|V2|≤|V1|+2|V2|=γ{Rk}(D),可得|V0|=|V2|=0,因此γk(D)=γ{Rk}(D)=n,2)得證.

下一步由2)證3).如果存在一個(gè)頂點(diǎn)v∈V(D)使得d-(v)≥k,則V{v}是D的一個(gè)k-控制集.因此,γk(D)≤n-1,矛盾！ 故3)成立.

最后由3)證1).由Δ-(D)≤k-1,可得γk(D)=n.由于γ{Rk}(D)≤n=γk(D),結(jié)合命題1可知1)成立.

命題4設(shè)f=(V0,V1,V2)是有向圖D的任意一個(gè)γ{Rk}(D)-函數(shù),則以下結(jié)論成立:

1)D[V1]不包含這樣的二部子圖: 它有一個(gè)二劃分(X,Y)滿足X中的每個(gè)頂點(diǎn)和Y中的任何一個(gè)頂點(diǎn)形成一條弧,且以X中的頂點(diǎn)為尾和Y中的頂點(diǎn)為頭,其中

|Y|=k+1;

2) 如果w∈V1,則|N-(w)∩V2|≤k-1;

4)V2是D的導(dǎo)出子圖D[V0∪V2]的一個(gè)γk-集;

證明1) 假設(shè)D[V1]包含一個(gè)符合題中條件的有向二部子圖,則f′=(V0∪Y,V1-(X∪Y),V2∪X)也是有向圖D的一個(gè)Romank-控制函數(shù),并且它的權(quán)值

ω(f′)=|V1-(X∪Y)|+2|V2∪X| =|V1|+2|V2|+|X|-|Y| =|V1|+2|V2|-1 =ω(f)-1.

這與f是有向圖D的一個(gè)γ{Rk}(D)-函數(shù)矛盾,因而1)得證.

2) 假設(shè)|N-(w)∩V2|≥k,則f′=(V0∪{w},V1{w},V2)也是有向圖D的一個(gè)Romank-控制函數(shù),并且ω(f′)=ω(f)-1.這與f是有向圖D的一個(gè)γ{Rk}(D)-函數(shù)矛盾,因而2)得證.

ω(f′)=|V1-B|+2|V2∪A|=|V1|+2|V2|+2|A|-|B|=|V1|+2|V2|-1=ω(f)-1.

這與f是有向圖D的一個(gè)γ{Rk}(D)-函數(shù)矛盾,因而3)得證.

4) 由f=(V0,V1,V2)是有向圖D的任意一個(gè)Romank-控制函數(shù)的定義可得結(jié)論.

5) 首先可知v有一個(gè)出鄰點(diǎn)在V0中,否則f′=(V0,V1∪{v},V2-{v})也是D的一個(gè)Romank-控制函數(shù),并且它的權(quán)值ω(f′)=ω(f)-1,這與f是有向圖D的一個(gè)γ{Rk}(D)-函數(shù)矛盾.

推論[1]設(shè)f=(V0,V1,V2)是有向圖D的任意一個(gè)γR(D)-函數(shù),則以下結(jié)論成立:

1) Δ+(D[V1])≤1;

4)V2是導(dǎo)出子圖D[V0∪V2]的一個(gè)γ-集;

5) 設(shè)H=D[V0∪V2],則在V2中每個(gè)滿足N-(v)∩V2≠?的頂點(diǎn)v至少有2個(gè)關(guān)于V2的副出鄰點(diǎn)在H中.

ω(f′)=|V1-{y}|+2|(V2-{v})∪{w}|=|V1|+2|V2|-1=ω(f)-1.

這與f是有向圖D的任意一個(gè)γR(D)-函數(shù)矛盾,證畢.

2 Roman k-控制數(shù)

首先,命題5給出了在一般情況下Romank-控制數(shù)的界; 然后,命題6、7、8給出了在一些限定條件下Romank-控制數(shù)的界; 最后給出了有向路和有向圈的Romank-控制數(shù)的值.分別記Pn和Cn為n階有向路和n階有向圈.

命題5設(shè)D是一個(gè)n階有向圖,則γ{Rk}(D)≥min{n,γk(D)+k}.

證明顯然γ{Rk}(D)≤n.如果γ{Rk}(D)=n,證畢.如果γ{Rk}(D)

|V1|+2|V2|=γ{Rk}(D)≤γk(D)+k-1≤|V1|+|V2|+k-1.

計(jì)算可得|V2|≤k-1.結(jié)合f=(V0,V1,V2)是有向圖D的一個(gè)γ{Rk}(D)-函數(shù)知|V0|=|V2|=0,所以γ{Rk}(D)=|V1|=n,這與假設(shè)γ{Rk}(D)

推論[1]設(shè)D是一個(gè)n階有向圖,則γR(D)≥min{n,γ(D)+1}.

命題6設(shè)D是一個(gè)n階有向圖,則下列結(jié)論成立:

1) 如果n≤2k,則γ{Rk}(D)=n;

2) 如果n≥2k+1,則γ{Rk}(D)≥2k;

3) 如果n≤2k+1,并且γk(D)=k,則γ{Rk}(D)=2k.

證明設(shè)f=(V0,V1,V2)是有向圖D的一個(gè)γ{Rk}(D)-函數(shù).顯然γ{Rk}(D)≤n.

1) 假設(shè)γ{Rk}(D)

2) 如果γ{Rk}(D)=n,因?yàn)閚≥2k+1,所以γ{Rk}(D)≥2k,證畢.如果γ{Rk}(D)

3) 設(shè)S是D的一個(gè)γk(D)-集,則f=(VS,?,S)是D的一個(gè)Romank-控制函數(shù),因此γ{Rk}(D)≤2|S|=2k,結(jié)合2)可知γ{Rk}(D)=2k,證畢.

給定一個(gè)有向圖D,如果頂點(diǎn)集V中僅有一個(gè)頂點(diǎn)v∈V的入度為0,且剩余任意頂點(diǎn)w∈V{v}與該頂點(diǎn)都存在(v,w)-路,則D叫做有向出樹(shù),其中v叫做有向出樹(shù)的根,出度為0的頂點(diǎn)叫做有向出樹(shù)的葉子.有向星圖是僅有一個(gè)頂點(diǎn)不是葉子的有向出樹(shù).

推論設(shè)D是一個(gè)n≥3階有向星圖,則γR(D)=2.

γ{Rk}(D)≤|V-(X∪Y)|+2|Y|=n-|X|+|Y|

命題8設(shè)D是一個(gè)n階有向圖,并且D的最大出度Δ+(D)≥k,則γ{Rk}(D)≥2n(Δ+/k+1).

證明設(shè)f=(V0,V1,V2)是一個(gè)γ{Rk}(D)-函數(shù).因?yàn)閂0的每個(gè)頂點(diǎn)至少有k個(gè)入鄰點(diǎn)在V2中,所以k|V0|≤Δ+|V2|,進(jìn)而可得

(Δ+/k+1)γ{Rk}(D)=(Δ+/k+1)(|V1|+2|V2|)=(Δ+/k+1)|V1|+2(Δ+/k+1)|V2|≥

(Δ+/k+1)|V1|+2|V0|+2|V2|≥2|V1|+2|V0|+2|V2|=2n.

證畢.

推論Ⅰ設(shè)D是一個(gè)n階有向圖,并且D的最大出度Δ+(D)=k,則γ{Rk}(D)=n.

推論Ⅱ設(shè)D是一個(gè)n階有向圖,并且D的最大出度Δ+(D)=1,則γR(D)=n.

有向路和有向圈的最大出度Δ+(D)=1,由推論Ⅱ可知它們的Roman控制數(shù)的值.在下面的命題中給出它們的Romank-控制數(shù)的值.

命題9γ{Rk}(Pn)=γ{Rk}(Cn)=n.

證明下面只需證明γ{Rk}(Pn)=n,γ{Rk}(Cn)=n可類(lèi)似證明.

設(shè)f是γ{Rk}(Pn)-函數(shù),對(duì)于每個(gè)滿足條件f(v)=0的頂點(diǎn)v,它至少有k個(gè)滿足條件

f(w)=2的入鄰點(diǎn)w.由于Pn是有向路,則其中每個(gè)頂點(diǎn)最多有一個(gè)入鄰點(diǎn).因此分下面2種情況討論:

當(dāng)k≥2時(shí),每個(gè)頂點(diǎn)v滿足f(v)=1,因此γ{Rk}(Pn)=n;

當(dāng)k=1時(shí),由推論Ⅱ可證.