有向圖出控制數與入控制數的和

郝國亮,錢建國

(廈門大學數學科學學院,福建廈門361005)

有向圖出控制數與入控制數的和

郝國亮*,錢建國

(廈門大學數學科學學院,福建廈門361005)

設S是有向圖D的一個頂點子集,若D的每個不在S中的頂點都鄰接自(到)S的某個(些)頂點,則稱S是D的出(入)控制集.D的出(入)控制數是D的出(入)控制集的最小基數.給出了有向圖關于出控制數與入控制數之和的上界,部分改進了Chartrand等給出的相應結果.

出控制數;入控制數;有向圖

1 預備知識

隨著計算機科學和網絡通信技術的發展,圖的控制集(dominating set)問題的研究受到了較大的關注.對無向圖控制集的研究已有較豐富的結果.1968年, Fu[1]把該問題引入到有向圖上.較之于無向圖,對有向圖控制集問題的研究相對較少[2-5].

本文分別用G=(V,E)和D=(V,A)表示簡單無向圖和簡單有向圖.如果(u,v)是D的一條弧,則稱u鄰接到v,或v鄰接自u.有向圖D中頂點v的出度記為d+D(v),v的入度記為dˉD(v).有向圖D的最小出度和最小入度分別為

δ+(D)=min{d+D(v):v∈V(D)},

δˉ(D)=min{dˉD(v):v∈V(D)}.

給定任意圖G,對于它的每條邊,給其端點指定一個順序,從而確定一條弧,由此得到一個有向圖,這樣的有向圖稱為G的一個定向.一般情況下圖G的定向不是唯一的.

設S?V(D),若D的每個不在S中的頂點都鄰接自(到)S的某個(些)頂點,則稱S是D的出(入)控制集.D中包含頂點數最少的出(入)控制集稱為D的最小出(入)控制集,它的基數稱為D的出(入)控制數,記為γ+(D)(γˉ(D)).顯然,入度為0的頂點屬于每個出控制集并且出度為0的頂點屬于每個入控制集.在此說明:D的出控制集和入控制集也可以分別稱為D的控制集和吸收集[6-7].

1999年,Chartrand等在文獻[8]中給出了γ+(D)+γˉ(D)的上界:

定理1[8]若D是不含孤立點的n階有向圖,則γ+(D)+γˉ(D)≤4n/3.

受此結果的啟發,本文研究有向圖的出控制數與入控制數,得到了有向圖關于出控制數與入控制數之和的上界,部分改進了Chartrand等給出的相應結果.

2 主要結果及證明

定理3 設D是n階有向圖,且δˉ(D)≥1,則

且此界是可達的.

證明 設H是包含孤立點數最少的D的一個頂點不交的有向星圖覆蓋.對于整數i≥1,設Hi是由H的所有同構于的連通分支構成的子有向圖,并設hi是Hi的連通分支數.顯然

易見在D中,H1的任意兩頂點間不存在弧,并且也不存在從到V(H1)的弧(否則,與H的假設矛盾).注意到,所以對于H1的任意頂點x,一定存在y∈V(H2)使得(y,x)∈A(D).設階為2的有向星圖uv∈H2,其中u是它的中心.則D中, v最多鄰接到H1的一個頂點,并且u不會鄰接到H1的任何一個頂點(否則,與H的假設矛盾).考慮到因為δˉ(D)≥1,所以h2≥δˉ(D)h1.

不難看出,S+(H)=V(H1)∪{u:u是Hi(i≥2)中某個有向星圖的中心}和Sˉ(H)=V(H1)∪{u:u是Hi(i≥2)中某個有向星圖的非中心的頂點}分別是H的出控制集和入控制集.注意到H是D的生成子有向圖,因此

由于

所以

為了說明此界是可達的,設D是頂點不交的3階有向圈的并,則由定理2可得

利用同樣的方法,可以得到下列結果,證明省略.

定理4 設D是n階有向圖,且δ+(D)≥1,則

且此界是可達的.

由定理3和定理4,可以自然地得到:

推論1 設D是n階有向圖,且δˉ(D)≥1, δ+(D)≥1,則

且此界是可達的.

星圖Sn是指n≥2階完全二部圖K1,nˉ1.星圖Sn中最大度頂點稱為它的中心.

引理1 設D是星圖Sn(n≥2)的定向,且v是Sn的中心,則

2.1.1 檢測波長的選擇 《中國藥典》2015年版記載，SMZ及其制劑定量檢測多采用240與254 nm，SDZ及其制劑定量檢測多采用260 nm，NOR及其制劑定量檢測多采用255～280 nm，OFL及其制劑定量檢測多采用290 nm，TC及其制劑定量檢測多采用280 nm、OTC及其制劑定量檢測多采用280 nm進行檢測。為保證待測物質均有較大吸收,本方法采用260 nm為檢測波長。

證明 設V(Sn)={v,v1,v2,…,vnˉ1}.若.易見{v}和V(Sn) {v}分別是D的最小出控制集和最小入控制集.若則不妨假設

不難驗證{v}∪{vi:k+1≤i≤nˉ1}和{v}∪{vi: 1≤i≤k}分別是D的最小出控制集和最小入控制集.由此可得

設M是圖G的一個邊子集,若M中任意兩條邊都不相鄰,則稱M是G的匹配.G中最大匹配的基數稱為G的匹配數,記作α′(G).

定理5 設D是n≥3階圖G的定向,且G不含孤立點,則

γ+(D)+γˉ(D)≤n+α′(G),

證明 注意到G不含孤立點,因此G含有一個生成子圖H使得H的每個連通分支Hi(i∈{1,2,…, k})都同構于某個階不小于2的星圖.對于每個i∈{1,2,…,k},設Di是由V(Hi)導出的D的子有向圖.因此由引理1可得γ+(Di)+γˉ(Di)≤|V(Di)|+1,其中i∈{1,2,…,k}.注意到α′(G),所以

為了說明此界是可達的,設D是星圖Sn(n≥3)的定向使得其中v是Sn的中心.注意到α′(Sn)=1.因此由引理1可得

設S是圖G的一個頂點子集,若S中任意兩個頂點都不相鄰,則稱S是G的獨立集.G中最大獨立集的基數稱為G的獨立數,記作α(G).

推論2 設D是n≥3階二部圖G的定向,且G不含孤立點,則

且此界是可達的.

證明 由于G是二部圖,所以α′(G)=nˉα(G).由定理5可得

為了說明此界是可達的,設D是星圖Sn(n≥3)的定向使得其中v是Sn的中心.注意到α(Sn)=nˉ1.因此由引理1可得

定理6 設D是n階圖G的定向,且δˉ(D)≥1, δ+(D)≥1,則

且此界是可達的.

證明 設I是G的一個最大獨立集.由于δˉ(D)≥1,所以對于任意的頂點u∈I,至少存在V(D)I中一個頂點鄰接到u.因此V(D)I是D的出控制集.另一方面,由于δ+(D)≥1,所以對于任意的頂點u∈I,至少存在V(D)I中一個頂點鄰接自u.因此V(D)I也是D的入控制集.由此可得

為了說明此界是可達的,設D是n階有向圈且G是D的基礎圖.注意到,由定理2可得

[1] Fu Y.Dominating set and converse dominating set of a directed graph[J].Amer Math Monthly,1968,75:861-863.

[2] Cai H,Liu J,Meng J.Domination number in iterated line digraph of a complete bipartite digraph[J].Ars Combin, 2012,107:515-520.

[3] Niepel L,Knor M.Domination in a digraph and in its reverse[J].Discrete Appl Math,2009,157:2973-2977.

[4] Niepel L,Knor M.Domination in the cross priduct of digraphs[J].Ars Combin,2010,97:271-279.

[5] Pang C,Zhang R,Zhang Q,et al.Dominating sets in directed graphs[J].Inform Sci,2010,180:3647-3652.

[6] Zhang X,Liu J,Chen X,et al.Domination number of Cartesian products of directed cycles[J].Inform Process Lett,2010,111:36-39.

[7] Shan E,Cheng T C E,Kang L.Absorbant of generalized de Bruijn digraphs[J].Inform Process Lett,2007,105: 6-11.

[8] Chartrand G,Harary F,Yue B Q.On the out-domination and indomination numbers of a digraph[J].Discrete Math,1999,197:179-183.

Sum of Out-domination Number and In-domination Number of Digraphs

HAO Guo-liang*,QIAN Jian-guo
(School of Mathematical Sciences,Xiamen University,Xiamen 361005,China)

:A vertex subset S of a digraph D is called an out-dominating(in-dominating)set of D if every vertex outside S is adjacent from(to)some vertexes in S.The out-domination(in-domination)number of a digraph D is the minimum cardinality of an out-dominating(in-dominating)set of D.We obtain some upper bounds on the sum of out-domination number and in-domination number of a digraph,which partially improve the result of Chartrand et al.

out-domination number;in-domination number;digraph

O 157.5

A

0438-0479(2015)03-0351-03

10.6043/j.issn.0438-0479.2015.03.010

2014-04-08 錄用日期:2014-10-15

國家自然科學基金(11271307)

*通信作者:guoliang-hao@163.com

郝國亮,錢建國.有向圖出控制數與入控制數的和[J].廈門大學學報:自然科學版,2015,54(3):351-353.

:Hao Guoliang,Qian Jianguo.Sum of out-domination number and in-domination number of digraphs[J].Journal of Xiamen University:Natural Science,2015,54(3):351-353.(in Chinese)