林上為，吳姝煜

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

0 引言和術(shù)語

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

D的最小出度是

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

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

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

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

則D是極大弧連通的。

文獻(xiàn)［4］給出另外一種類型的度條件。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證明 因?yàn)閷θ我獾膗∈V(D)都有d(u)≤n－1，所以除可能的一個(gè)點(diǎn)外，滿足題設(shè)條件的D的所有頂點(diǎn)的度都至少為

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

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

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

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

對兩個(gè)互相配對的頂點(diǎn)x，x′∈X′，有

記

則

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

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

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

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

情形1k≤2。

此 時(shí)，ξ′(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。

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

2 對結(jié)果的討論

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

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

是基數(shù)都為p的4個(gè)不相交集合，其中p≥3。設(shè)H1和H2是 頂 點(diǎn) 集 分 別 為V(H1)=U∪X和V(H2)=V∪Y的兩個(gè)完全無向圖。設(shè)H3是具有二劃分(U，V)的1-正則二部無向圖并且設(shè)H4是具有二劃分(X，Y)的 2- 正 則 二 部 無 向 圖 。 設(shè)G是 并 圖H1∪H2∪H3∪H4，設(shè)有向圖D是圖G的完全雙定向。 對 任 意 的 一 個(gè) 點(diǎn) 對{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)是一個(gè)限制弧割，從而有