有向圖的Roman k-控制

張曉轉, 孟 巍

(山西大學 數學科學學院，山西 太原 030006)

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

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

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

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

Kammerling和Volkmann在文獻[3]中給出了無向圖的Roman k-控制數的一些性質.我們對這些性質進行了推廣,首先給出了有向圖中Roman k-控制數的一些性質,然后給出了一些特殊有向圖的Roman k-控制數的界.

1 Roman k-控制數的一些性質

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

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

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

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

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

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

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

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

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

命題3設D是一個n階有向圖,則以下3條等價:

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

2)γk(D)=n;

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

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

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

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

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

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

|Y|=k+1;

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

4)V2是D的導出子圖D[V0∪V2]的一個γk-集;

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

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

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

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

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

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

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

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

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

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

4)V2是導出子圖D[V0∪V2]的一個γ-集;

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

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

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

2 Roman k-控制數

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

命題5設D是一個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.

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

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

命題6設D是一個n階有向圖,則下列結論成立:

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

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

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

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

1) 假設γ{Rk}(D)

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

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

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

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

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

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

證明設f=(V0,V1,V2)是一個γ{Rk}(D)-函數.因為V0的每個頂點至少有k個入鄰點在V2中,所以k|V0|≤Δ+|V2|,進而可得

(Δ+/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.

證畢.

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

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

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

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

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

設f是γ{Rk}(Pn)-函數,對于每個滿足條件f(v)=0的頂點v,它至少有k個滿足條件

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

當k≥2時,每個頂點v滿足f(v)=1,因此γ{Rk}(Pn)=n;

當k=1時,由推論Ⅱ可證.