非極大弧連通定向圖弧連通度的下界

王曉麗,張雪霞

(晉中學院 數學系，山西 榆次 030619)

0 引言

對任何一個有向圖，它的弧連通度λ與最小度δ滿足λ≤δ，當λ=δ時， 稱有向圖D是極大弧連通的,說明最小度δ是弧連通度λ的上界.Chartrand 和Harary已經對圖的點連通度的下界進行了研究.Topp和Volkmann得出了二部圖相似的下界.但對于非極大弧連通圖的弧連通度的下界結論很少.本文考慮定向圖D滿足團數ω(D)≤p時，把無向圖的Turán定理的結論推廣到定向圖，利用函數的凸性來研究定向圖的弧連通度，得出了非極大弧連通定向圖弧連通度的下界.本文未給出的術語和記號請參見文獻[1].

1 預備知識

定義1[1]頂點v的度

d(v)=min{d+(v),d-(v)}，

其中d+(x)和d-(x)分別表示頂點v的出度和入度.

定義2[1]沒有2-圈且沒有環的有向圖稱為定向圖.

定義3[1]有向圖D的最小度

δ=min{δ+,δ-}，

其中δ+和δ-分別表示D的最小出度和最小入度.

定義4[2]如果去掉有向圖D的弧的方向，再去掉產生的重邊得到的簡單圖UG(D)不含p+1個頂點的團，稱有向圖D的團數ω(D)≤p.

定義5[2]若n階有向圖D的頂點集為{v1,v2,…,vn}，有向圖D的度序列定義為頂點度的不增序列(d1,d2,…,dn)，即d1≥d2≥…≥dn=δ.

引理1[3](Turán定理)設整數p≥1,若圖G不含完全子圖Kp+1，則

引理2[4]f(x)是[L,R]上的連續凸函數，若l,r∈[L,R]，滿足l+r=L+R，則

f(L)+f(R)≥f(l)+f(r).

2 主要結論

證明因為D是定向圖，所以D的弧數與UG(D)的弧數相等，即

m(D)=m(UG(D))=m.

又因為D的團數ω(D)≤p，所以ω(UG(D))≤p.由引理1知，

定理2若D是團數ω(D)≤p的n階定向圖，任取頂點集S?V(G),|S|=k,則

證明(1)若UG(D[S])不含p個頂點的團，則

(2)若UG(D[S])包含p個頂點的團，取頂點集Q?S,UG(Q)是不包含p個頂點的團的頂點數最多的頂點集.設|Q|=l,則D的每個頂點的鄰集的導出子圖不包含p個頂點的團.假設D的頂點v1的鄰集的導出子圖包含p個頂點的團，則UG(D)包含p+1個頂點的團，與定向圖D的團數ω(D)≤p矛盾，所以D的每個頂點的鄰集的導出子圖不包含p個頂點的團.

|N(v1)|>l，

則N(v1)不包含p個頂點的團，但|N(v1)|>l，與頂點集Q的選取矛盾，所以v在S中最多有l個鄰點.

則

因此

證明令φp(k,x)=

定理4設D是一個團數W(D)≤P的n階強連通定向圖,D的不增度序列為(d1,d2,…,dn)，若λ<δ，則

其中

1≤k≤a,a=max2δ+1,2pδp-1{}.

證明因為λ<δ，故存在兩個不相交的集合X,Y?V(D),滿足X∪Y=V(D),|(X,Y)|=λ<δ,使得|X|、|Y|≥2δ+1[2].

(反證法)假設X,Y?V(D)滿足X∪Y=V(D)且|(X,Y)|=λ<δ,使得|X|≤2δ.

同理可證|Y|≥2δ+1.

將X、Y中的頂點按頂點度從大到小排列，選S，T分別是排好序后的X，Y中前k個頂點組成的集合.其中

1≤k≤a,a=max2δ+1,2pδp-1{}.

由于定向圖D不含p+1個頂點的團，所以D[X],D[Y]也不含p+1個頂點的團.

在D[X],D[Y]中，由定理2知

因此

同理

故

由S、T的選取知S∪T包含D的k個最高度頂點，但不含D的a-k個最低度的頂點.

即

推論設D是一個團數W(D)的n階強連通定向圖,D的不增度序列為(d1,d2,…,dn)，若λ<δ，則

證明由定理4，k=1時，

3 結語

本文利用函數的凸性研究了定向圖的弧連通度.當定向圖D滿足團數ω(D)≤p時，分析弧連通度與度序列之間的關系，得出非極大弧連通定向圖弧連通度的下界，也可以利用函數的凸性研究定向圖極大和超級弧連通的度序列條件.