極大限制弧連通有向圖的度條件

林上為，吳姝煜

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

0 引言和術(shù)語

對于這里沒有定義的圖論術(shù)語和符號，請參見文獻［1］。本文討論的有向圖都是有限的且沒有環(huán)和多重弧。對有向圖D，用V=V(D)和A=A(D)分別表示D的頂點集和弧集。對有向圖D中的一個頂點v，它的外鄰域為N+(v)={u∈V(D)：vu∈A(D)}，出度為

D的最小出度是

點v的內(nèi)鄰域N－(v)，入度d－(v)和D的最小入度δ－(D)可類似定義。頂點v的度定義為d(v)=min {d+(v)，d－(v)}，有 向 圖D的 最 小 度 定 義 為δ(D)=min {d(v)：v∈V(D)}=min {δ+(D)，δ－(D)}。對于非空頂點子集對X，Y和D的弧子集S，記S(X，Y)={xy∈S：x∈X，y∈Y}。若Y=Xˉ，則用A+(X)或者A－(Y)表示

若有向圖D中任意兩個頂點互相可達，那么稱有向圖D是強連通的。約定只有一個頂點的有向圖是強連通的。稱有向圖D的極大強連通子圖為D的強連通分支。一個強連通分支是平凡的，如果它只包含一個頂點。對強連通有向圖D，稱S?A(D)是有向圖D的一個弧割，如果D－S是不強連通的。有向圖D的一個最小弧割的弧數(shù)稱為D的弧連通度，記為λ(D)。

眾所周知，當(dāng)用有向圖為有向互聯(lián)網(wǎng)絡(luò)建模時，有向圖的弧連通度越大，對應(yīng)網(wǎng)絡(luò)越可靠。且對所有有向圖D都有λ(D)≤δ(D)成立，稱滿足λ(D)=δ(D)的強連通有向圖D為極大弧連通的。極大弧連通有向圖的充分條件曾得到廣泛的研究[2]。特別地，文獻［3］給出極大弧連通圖的一個度條件。

定理1[3]設(shè)D是一個n階有向圖。若所有滿足uv?A(D)的點對{u，v}都有

則D是極大弧連通的。

文獻［4］給出另外一種類型的度條件。

則有向圖D是極大弧連通的。

為了將Esfahanian 和Hakimi[5]提出的無向圖的限制邊連通度推廣到有向圖，Volkmann[6]引入了限制弧連通度的概念。設(shè)D是一個強連通有向圖。稱D的一個弧割S是D的一個限制弧割，如果DS有一個非平凡的強連通分支D1使得D－V(D1)包含一條弧。如果強連通有向圖D中存在一個限制弧割，則稱D是λ′-連通的。一個λ′-連通有向圖D的限制弧連通度λ′(D)是D的一個最小限制弧割所含的弧數(shù)。

2008 年，Wang 和Lin[7]在研究限制弧連通度上界時引進弧度的概念。對有向圖D的一條弧xy，記

將弧xy的弧度定義為ξ′(xy)=min {|S|：S∈Ωxy}，有向圖D的最小弧度定義為

文獻［7］也證明了以下結(jié)果。

定理3[7]設(shè)D是一個滿足δ+(D)≥3 或者δ－(D)≥3 的強連通有向圖，那么有向圖D是λ′-連通的且λ′(D)≤ξ′(D)。

2013 年，Balbuena 等[8]證 明 了 一 個 類 似 的結(jié)果。

定理4[8]設(shè)D是階數(shù)至少為4 的強連通有向圖。如果D的最小度δ(D)≥2，那么D是λ′-連通的且λ′(D)≤ξ′(D)。

由定理3 和定理4 可知對大多數(shù)有向圖D，最小弧度ξ′(D)是限制弧連通度λ′(D)的上界。據(jù)此，文獻［7］引入了極大限制弧連通圖的概念。稱一個λ′-連通有向圖D是極大限制弧連通的，如果λ′(D)=ξ′(D)。近年來，限制弧連通度得到了一些研究［9-12］，這其中極大限制弧連通有向圖的充分條件尤其受到關(guān)注，比如度條件［13-17］，直徑圍長條件[18]和鄰域條件[19]。特別地，文獻［7］也證明了極大限制弧連通有向圖的一個鄰域交條件。與定理1 同樣考慮，可由鄰域交條件得下面的度條件。

定理5[7]設(shè)D是一個n階有向圖。若所有滿足uv?A(D)的點對{u，v}都有

則D是極大限制弧連通的。

本文將沿定理2 的思路，給出與定理5 不同的極大限制弧連通有向圖的一個度條件。在最后也給出例子說明本文得出的結(jié)果與定理5 的結(jié)果是獨立的并且在某種意義上本文所得的結(jié)果是最優(yōu)的。

1 極大限制弧連通有向圖的度條件

在給出主要結(jié)果之前，先介紹兩個引理。由文獻［8］中定理1.2 的證明可得下面的引理1。

引 理1[8]設(shè)D是 一 個 滿 足λ′(D)≤ξ′(D)的λ′-連通有向圖，且設(shè)S是D的一個最小限制弧割，那么要么存在一個頂點子集X?V(D)使得導(dǎo)出子圖D[X]和D[V－X]中都至少包含一條弧且S=A+(X)，要 么 存 在 一 條 弧uv∈A(D) 使得S∈Ωuv。

引理2 設(shè)D是一個階數(shù)為n≥4 的強連通有向圖。若除可能的一個點外，D的所有頂點的度都至 少 為 3，則 有 向 圖D是λ′- 連 通 的 且λ′(D)≤ξ′(D)。

證明 對任意給定的一條弧xy∈A(D)，因為除可能的一個點外，D中所有頂點的度都至少為3，所以除可能的一個點外，D－{x，y}中所有頂點的度都至少為1。這說明D－{x，y}包含一個圈。因此，D－{x，y}有一個非平凡的強連通分支D1。對任意的S∈Ωxy，D1也是D－S的一個非平凡的強連通分支并且D－V(D1)含弧xy。這說明S是一個限制弧割，從而D是λ′-連通的并且λ′(D)≤|S|。由弧xy的任意性和S的任意性可得λ′(D)≤ξ′(D)。

則D是極大限制弧連通的。

證明 因為對任意的u∈V(D)都有d(u)≤n－1，所以除可能的一個點外，滿足題設(shè)條件的D的所有頂點的度都至少為

由引理2，D是λ′-連通的且λ′(D)≤ξ′(D)。用反證法，假設(shè)D不是極大限制弧連通的，則有λ′(D)＜ξ′(D)。設(shè)S是D的一個最小限制弧割。若存在一條弧xy使得S∈Ωxy，則λ′(D)=|S|≥ξ′(D)，矛盾。因此，由引理1，存在一個頂點子集X?V(D)使得D[X]和D[Y]都包含至少一條弧且S=A+(X)，其中Y=V(D)－X。顯然，|X|≥2。若|X|=2，則可設(shè)X={x，y} 且xy是 一 條 弧。此 時S=A+(X)=A+({x，y})∈Ωxy。從而，

λ′(D)=|S|=|A+({x，y})|≥ξ′(D)，矛盾。

因此，|X|≥3。同理可得|Y|≥3。記p=|X|和q=|Y|。不失一般性，假設(shè)p≤q。

設(shè)Y′={y∈Y： 存 在 一 個 頂 點y′∈Y使得{y，y′}∈π(D)}，Yi={y∈Y：存在一個頂點x∈Xi使得{x，y}∈π(D)}，i=0，1，2，3，4。 顯 然有

對任意的i∈{0，1，2，3}和y∈Yi，存在一個頂點x∈Xi使得{x，y}∈π(D)，因此

整理得|S(X，y)|≥4－i，從而有|S(X，Yi)|≥(4－i)|Yi|=(4－i)|Xi|。因此

將（2）式和（3）式相加，得到

對兩個互相配對的頂點x，x′∈X′，有

記

則

記|Y′|=2t，同理可得

若n是偶數(shù)，則D中所有點都是配對點，因此

設(shè)x1，x2是X中一對頂點，使得x1和x2之間有弧且|S(x1，Y)|+|S(x2，Y)|最小。記

下面對k的取值分情況討論，得到想要的矛盾。

情形1k≤2。

此 時，ξ′(D)≤|A+({x1，x2})|=A({x1，x2}，|X－{x1，x2})|+|S(x1，Y)|+|S(x2，Y)|≤2|X－{x1，x2}|+|S(x1，Y)|+|S(x2，Y)|=2(p－2)+|S(x1，Y)|+|S(x2，Y)|=2(p－2)+k≤2(p－1)。結(jié) 合（8）式 有λ′(D)≥ξ′(D)，與 假 設(shè)λ′(D)＜ξ′(D)矛盾。

情形2k≥3。

不妨設(shè)|S(x1，Y)|≤|S(x2，Y)|。設(shè)

則有

和

對任意的x∈W1∪W3，有弧x1x。由x1x2的選取有

由此可得對任意的x∈W1∪W3，

同 理，對 任 意 的x∈W2，有|S(x，Y)|+|S(x2，Y)|≥|S(x1，Y)|+|S(x2，Y)|，由此可得對任意的x∈W2，

情形2.1 |S(x1，Y)|≥1。

若|S(x1，Y)|=1，則

|S(x2，Y)|=k－|S(x1，Y)|≥3－1=2。

若|S(x1，Y)|≥2，則

|S(x2，Y)|≥|S(x1，Y)|≥2。

綜上都有|S(x2，Y)|≥2。

由（11）式和（12）式可知，對任意的x∈W1∪W3有|S(x，Y)|≥|S(x2，Y)|≥2，且 對 任 意 的x∈W2有|S(x，Y)|≥|S(x1，Y)|≥1。再結(jié)合（9）式和（10）式可得λ′(D)≥k+2|W1|+2|W3|+|W2|≥k+|W1|+|W2|+2|W3|≥ξ′(D)，矛盾。

情形2.2 |S(x1，Y)|=0。

此時|S(x2，Y)|=k。結(jié)合（9）式和（11）式有

由（8）式可得

結(jié)合（10）式、（14）式和假設(shè)可得

整理得

結(jié) 合（10）式、（13）式 和 假 設(shè) 可 得k+|W1|+|W2|+2|W3|≥ξ′(D)＞λ′(D)≥k+k|W1|+k|W3|，整理得

結(jié)合（15）式和（16）式有

由此可得

這 說 明N+(x1)∩(X－{x1，x2})=?， 又 由|S(x1，Y)|=0，故N+(x1)?{x2}，從而d+(x1)≤1。

由（17）式可知，W2≠?，若W2中一點x′1使得|S(x′1，Y)|=0， 則x2x′1是 一 條 弧 ， 且|S(x′1，Y)|+|S(x2，Y)|=k，同上面對x1，x2的討論可得d+(x′1)≤1，此時圖D中有兩個度小于等于1的頂點x1和x′1，與（1）矛盾。因此，對W2中任意一點x′1都有|S(x′1，Y)|≥1。再結(jié)合（9）式、（10）式和（18）式 可 得λ′(D)≥k+|W2|≥ξ′(D)，與 假 設(shè)λ′(D)＜ξ′(D)矛盾。定理得證。

2 對結(jié)果的討論

則稱有向圖D具有性質(zhì)Pk。定理2 表明，若一個有向圖具有性質(zhì)P0，則該圖是極大弧連通的。本文證明了每個滿足性質(zhì)P2的有向圖都是極大限制弧連通的。下面用例子說明，由性質(zhì)P1不能推出極大限制弧連通性，因此定理6 在某種意義上是最優(yōu)可能。

例1 設(shè)U={u1，u2，···，up}，

是基數(shù)都為p的4個不相交集合，其中p≥3。設(shè)H1和H2是 頂 點 集 分 別 為V(H1)=U∪X和V(H2)=V∪Y的兩個完全無向圖。設(shè)H3是具有二劃分(U，V)的1-正則二部無向圖并且設(shè)H4是具有二劃分(X，Y)的 2- 正 則 二 部 無 向 圖 。 設(shè)G是 并 圖H1∪H2∪H3∪H4，設(shè)有向圖D是圖G的完全雙定向。 對 任 意 的 一 個 點 對{u，v}∈{{u1，y1} ，{u2，y2} ，…，{up，yp} ，{v1，x1} ，·· ·，{vp，xp} }都有

d(u)+d(v)=2p+(2p+1)=|V(D)|+1，因此D具有性質(zhì)P1。但是A+(U∪V)是一個限制弧割，從而有