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

徐 蘭

(昌吉學院數學系,新疆昌吉 831100)

0 引 言

本文只考慮D=(V,A)是一個沒有自環和平行弧的有向圖.設點 v∈V,分別用 d-D(v)、d+D(v)(簡寫為,d-(v)、d+(v)),記為 v的出度、入度,δ-(D)、δ+(D)為 D的最小入度、最小出度,且D的最小度記為,δ(D)=min{δ-(D),δ+(D)}.

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

無孤立點的有向圖D的逆度定義為:

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

1 主要結果

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

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

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

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

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

定理1 設D為強連通的有向圖,其弧連通度為λ,最小度為δ.如果,

則,λ=δ.

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

根據引理2之(1)有,

又因為,λ≤δ-1,則,

矛盾.

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

則,λ=δ.

下面用實例說明定理中的界是緊的.

例1 設 n和δ是正整數,且 n≥2δ+2≥8,進一步,設 K→δ+1的點集為,V(K→δ+1)={x1,x2,…, xδ+1},K→n-δ-1的點集為,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)=δ,且,

容易得到,

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

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

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

則,λ=δ.

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

因為D[X]是二部有向子圖,則,

下面分3種情形進行討論.

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

所以,

矛盾.

情形2 n是偶數,且|X|是奇數.則,|Y|= n-|X|是奇數,有,|X|,|Y|≥2δ+1.和情形1類似,有,

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

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

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

下例說明定理中的界是緊的.

例2 設 n,δ為正整數,且 n是偶數,n≥4δ,設D是由K→δ,δ=(A,B)與K→n/2-δ,n/2-δ=(C,D)的不交并得來的.這里,(A,B)與(C,D)是二部劃分.分別在A與C中選擇δ-1個獨立點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.