王晓丽,张雪霞

(晋中学院 数学系，山西 榆次 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的邻集的导出子……