有向圖是極大弧連通的充分條件

徐 蘭

(昌吉學(xué)院數(shù)學(xué)系,新疆昌吉 831100)

0 引 言

本文只考慮D=(V,A)是一個(gè)沒(méi)有自環(huán)和平行弧的有向圖.設(shè)點(diǎn) v∈V,分別用 d-D(v)、d+D(v)(簡(jiǎn)寫(xiě)為,d-(v)、d+(v)),記為 v的出度、入度,δ-(D)、δ+(D)為 D的最小入度、最小出度,且D的最小度記為,δ(D)=min{δ-(D),δ+(D)}.

強(qiáng)連通有向圖D的弧割,是指去掉這個(gè)弧割后D不再?gòu)?qiáng)連通.弧連通度λ(D)是一個(gè)最小弧割的基數(shù).D是極大弧連通的,如果λ=δ.設(shè)X,Y?V,且(X,Y)表示尾巴在X中,頭在 Y中的弧集.和 K→n,m分別是完全有向圖與完全二部有向圖.文中未提到的定義與術(shù)語(yǔ)可參見(jiàn)文獻(xiàn)[1]中相關(guān)表述.

無(wú)孤立點(diǎn)的有向圖D的逆度定義為:

圖的逆度最早在文獻(xiàn)[2]中被提出,且被許多作者研究[3,5].本文將給出關(guān)于R(D)、δ(D)和 n階有向圖是極大弧連通的充分條件.

1 主要結(jié)果

引理1[6]設(shè)D為強(qiáng)連通的有向圖,其弧連通度為λ.如果存在不交集合,X,Y?V(D),有X∪Y =V(D),|(X,Y)|=λ＜δ,那么,|X|,|Y|≥δ+1.

引理2[4](1)設(shè) a1,a2,…,ap,A是正實(shí)數(shù),且

(2)如果 a1,a2,…,ap,A是正整數(shù),且 a,b是整數(shù),有A=ap+b,0≤b＜p,則,

等式成立的充要條件是p-b個(gè)ai等于a,其余的ai等于a+1.

(3)設(shè)f(x)是在[L,R]上的連續(xù)凸函數(shù),且l, r∈[L,R],l+r=L+R,則,

定理1 設(shè)D為強(qiáng)連通的有向圖,其弧連通度為λ,最小度為δ.如果,

則,λ=δ.

證明 假設(shè),λ≤δ-1.由引理1,存在不交集合 X,Y?V(D),使得,X∪Y=V(D)和|(X,Y) |=λ＜δ.有,δ+1≤|X|,|Y|≤n-δ-1.則,

根據(jù)引理2之(1)有,

又因?yàn)?λ≤δ-1,則,

矛盾.

推論1[4]設(shè) G是n階連通圖,其最小度為δ,邊連通度為λ,如果,

則,λ=δ.

下面用實(shí)例說(shuō)明定理中的界是緊的.

例1 設(shè) n和δ是正整數(shù),且 n≥2δ+2≥8,進(jìn)一步,設(shè) K→δ+1的點(diǎn)集為,V(K→δ+1)={x1,x2,…, xδ+1},K→n-δ-1的點(diǎn)集為,V(K→n-δ-1) = {y1,y2,…, yn-δ-1}.定義圖 D是K→δ+1與K→n-δ-1的并集,再加上2(δ-1)條弧,x1y1,x2y2,…,xδ-1yδ-1;y1x1,y2x2,…,yδ-1xδ-1.則,δ(D)=δ,且,

容易得到,

設(shè)D是二部有向圖,其二部分化為,V(D)=V′∪V″.設(shè)X是V(D)的子集,令X′=X∩V′,X″= X∩V″.

引理3[6]設(shè)D是強(qiáng)連通的二部圖,其弧連通度為λ,最小度為δ.如果λ＜δ,則存在不交集合X,Y?V(G),且 X∪Y=V(G),|(X,Y)|=λ,使得,|X′|,|X″|,|Y′|,|Y″|≥δ,即,|X|, |Y|≥2δ(G).

定理2 D是n階強(qiáng)連通的二部圖,其弧連通度為λ,最小度為δ.如果,

則,λ=δ.

證明 假設(shè),λ ≤δ-1,則存在,X,Y?V(D),X∪Y=V(D),|(X,Y)|=λ,使得,|X|, |Y|≥2δ(D).因此,δ≤

因?yàn)镈[X]是二部有向子圖,則,

下面分3種情形進(jìn)行討論.

情形1 n是偶數(shù),且|X|是偶數(shù).則,|Y|= n-|X|也是偶數(shù).由上面的不等式有,

所以,

矛盾.

情形2 n是偶數(shù),且|X|是奇數(shù).則,|Y|= n-|X|是奇數(shù),有,|X|,|Y|≥2δ+1.和情形1類(lèi)似,有,

通過(guò)計(jì)算可知,(2)大于(1),矛盾.

情形3 n是奇數(shù).不失一般性,設(shè)|X|是奇數(shù),且|Y|是偶數(shù).則,|X|≥2δ+1.類(lèi)似情形1, 2,有,

通過(guò)計(jì)算可知,(3)大于(1),矛盾.

下例說(shuō)明定理中的界是緊的.

例2 設(shè) n,δ為正整數(shù),且 n是偶數(shù),n≥4δ,設(shè)D是由K→δ,δ=(A,B)與K→n/2-δ,n/2-δ=(C,D)的不交并得來(lái)的.這里,(A,B)與(C,D)是二部劃分.分別在A與C中選擇δ-1個(gè)獨(dú)立點(diǎn)a1,a2,…,aδ-1和c1,c2,…,cδ-1,并添加2(δ-1)條弧 a1c1,a2c2,…, aδ-1cδ-1;c1a1,c2a2,…,cδ-1aδ-1,則 D是二部圖,且λ=δ-1及逆度為,

定理中的界是緊的得證.

[1]BondyJ A,Murty U S R.Graph Theory and Its Application[M]. London:Academic Press,1976.

[2]Fajtlowicz S.On Conjectures of Graffiti(II)[J].Congr Numer, 1987,60(1):189-197.

[3]Dankelmann P,Swart H C,van den Berg P.Diameter and Inverse Degree[J].Discrete Math,2008,308(5-6):670-673.

[4]Dankelmann P,Hellwig A,Volkmann L.Inverse Degree and Edge-connectivity[J].Discrete Math,2009,309(9):2943-2947.

[5]Erdǒs P,Pach J,Spencer J.On the Mean Distance Between Points of a Graph[J].Congr Number,1988,64(1):121-124.

[6]Hellwig A,Volkmann L.Maximally Connected Graphs[D].Hellwig,Angelika:RWTH Aachen University,2005.

[7]Geller D,Harary F.Connectivity in Digraphs[J].Lecture Notes in Mathematics,1971,186(1):105-115.