有向圖最小圈長不大于4的一個充分條件

梁 浩, 徐俊明

(1. 西南財經(jīng)大學 經(jīng)濟數(shù)學學院, 成都 611130； 2. 中國科學技術大學 數(shù)學科學學院, 合肥 230026)

設G=(V,E)是簡單有向圖(即不含環(huán)和平行邊), 其中:V=V(G)表示G的頂點集;E=E(G)表示G的邊集.

猜想1中, 對于r=n/3這一特殊情形受到了較多的關注： 當含有n個頂點的有向圖中頂點的最小出度不小于n/3時, 圖中一定存在長度不大于3的有向圈. 由于簡單有向圖不含環(huán)和平行邊, 此時圖中一定存在有向三角形. 這一簡單猜想至今仍然未被證明, 于是人們考慮從另一個方向給出一些近似結(jié)果, 即尋找一個盡可能小的常數(shù)α, 使得當最小出度不大于αn時, 圖中一定存在長度不大于3的有向圈, 即猜想1中的α=1/3. Caccetta等[1]證明了α<0.381 9時的結(jié)果, 之后文獻[6-8]對其進行了改進. Hladk等[9]將該結(jié)果改進為α<0.346 5, 即任意含有n個頂點的有向圖中頂點的最小出度不小于0.346 5n時, 圖中一定存在長度不大于3的有向圈. 本文考慮盡可能小的常數(shù)α, 使得當最小出度不大于αn時, 圖中必存在長度不大于4的有向圈, 猜想中α=1/4.

定理1若α≥0.288 66, 則n個頂點且最小出度不小于αn的有向圖中一定存在圈長不大于4的有向圈.

對任意的頂點v∈V(G), 令N+(v)={u∈V(G): (v,u)∈E(G)}, deg+(v)=|N+(v)|稱為v的出度；N-(v)={u∈V(G): (u,v)∈E(G)}, deg-(v)=|N-(v)|稱為v的入度.

如果(u,v),(u,w),(v,w)∈E(G), 則稱〈u,v,w〉是定向三角形. 其中(u,v)稱為定向三角形的基, 頂點u稱為定向三角形的源點. 如果(u,v),(v,w)∈E(G), 但u與w之間不連邊, 則稱uvw是長為2的導出子路. 對任意的(u,v)∈E(G), 令P(u,v)=N+(v)N+(u), 由定義可知p(u,v)=|N+(v)N-(u)|表示以(u,v)為第一條邊長為2的導出子路的數(shù)目.Q(u,v)=N-(u)N-(v), 類似可知q(u,v)=|N-(u)N-(v)|表示以(u,v)為第二條邊長為2的導出子路的數(shù)目.T(u,v)=N+(u)∩N+(v), 則t(u,v)=|N+(u)∩N+(v)|表示以(u,v)為基的定向三角形的數(shù)目.

引理1對任意的(u,v)∈E(G), 有

n>r+deg-(v)+q(u,v)+(1-α)r+(1-α)2t(u,v).

(1)

證明： 對(u,v)∈E(G), 當t(u,v)=0時, 不等式(1)簡化為

n>r+deg-(v)+q(u,v)+(1-α)r.

(2)

在以N+(v)為頂點的導出子圖中, 至少存在一個頂點w, 它在以N+(v)為頂點的導出子圖中的出度小于αr. 否則由歸納假設可知, 在這個頂點數(shù)為r的導出子圖中必存在長度不大于4的有向圈. 因此, |N+(w)N+(v)|≥r-αr. 再由假設條件,G中有向圈的長度都大于4, 可知N+(v),N+(w)N+(v),N-(v)及N-(u)N-(v)是兩兩不交的點集, 故有

n>|N+(v)|+|N-(v)|+|N-(u)N-(v)|+|N+(w)N+(v)|≥r+deg-(v)+q(u,v)+(1-α)r.

從而當t(u,v)=0時, 式(1)成立.

當t(u,v)>0時, 至少存在一個頂點w∈N+(u)∩N+(v), 在以N+(u)∩N+(v)為頂點的G的導出子圖中,w的出度小于αt(u,v), 否則由歸納假設, 在此導出子圖中必存在長度不大于4的有向圈, 故有

|N+(w)∩(N+(u)∩N+(v))|<αt(u,v).

(3)

另一方面,N+(w)包含于N+(v)N+(u)中的頂點數(shù)目滿足

|N+(w)∩(N+(v)N+(u))|≤|N+(v)N+(u)|=p(u,v).

(4)

注意到t(u,v)=r-p(u,v), 綜合式(3),(4)并代入

|N+(w)N+(v)|=|N+(w)|-|N+(w)∩(N+(u)∩N+(v))|-|N+(w)∩(N+(v)N+(u))|

可得

|N+(w)N+(v)|≥r-αt(u,v)-p(u,v)=(1-α)t(u,v).

(5)

由歸納假設,G中不含有向三角形, 故N+(w)N+(v),N-(u)N-(v),N-(v)是兩兩不交的點集. 考慮G中以N+(v)∪N+(w)為頂點的導出子圖. 根據(jù)歸納假設, 存在頂點x∈N+(v)∩N+(w), 在此導出子圖中,x的出度小于α|N+(v)∪N+(w)|. 于是N+(x)中落在N+(v)∪N+(w)以外的頂點數(shù)目滿足

即

|N+(x)(N+(v)∪N+(w))|≥(1-α)r-α|N+(w)N+(v)|.

(6)

由于G中不含長為4的有向圈, 故N+(x)(N+(v)∪N+(w)),N-(u)N-(v),N-(v)也是兩兩不交的點集. 于是N-(v),N+(w)N+(v),N+(x)(N+(v)∪N+(w)),N-(u)N-(v),N-(v)為兩兩不交的點集, 其頂點數(shù)目分別為r,|N+(w)N+(v)|,|N+(x)(N+(v)∪N+(w))|,q(u,v)和deg-(v), 故

n>r+|N+(w)N+(v)|+|N+(x)(N+(v)∪N+(w))|+q(u,v)+deg-(v).

(7)

將式(5),(6)代入式(7)得

證畢.

下面證明定理1. 注意到t(u,v)=r-p(u,v), 將不等式(1)重寫為

(2α-α2)t(u,v)>(3-α)r-n+deg-(v)+q(u,v)-p(u,v).

(8)

兩端對所有的(u,v)∈E(G)求和, 可得

(9)

(10)

其中t表示G中定向三角形的數(shù)目. 再由Cauchy不等式得

即

(11)

(12)

在式(8)兩端對所有的(u,v)∈E(G)求和, 并將式(9)～(12)代入可得

(2α-α2)t>(4-α)nr2-n2r.

(13)

(14)

比較式(13),(14)有

(4-α)nr2-n2r<(nr2/2)(2α-α2).

(15)

[1] Caccetta L, Haggkvist R. On Minimal Digraphs with Given Girth [C]//Proc 9th S-E Conf Combinatorics, Graph Theory and Computing. Boca Raton: Utilitas Mathematica Publishing, Inc, 1978: 181-187.

[2] Hamidoune Y O. A Note on Minimal Directed Graphs with Given Girth [J]. J Combin Theory: Ser B, 1987, 43(3): 343-348.

[3] Hoang C, Reed B. A Note on Short Cycles in Digraphs [J]. Discrete Math, 1987, 66(1/2): 103-107.

[4] SHEN Jian. On the Girth of Digraphs [J]. Discrete Math, 2000, 211(1/2/3): 167-181.

[5] Sullivan B D. A Summary of Results and Problems Related to the Caccetta-Haggkvist Conjecture [J/OL]. 2006-05-24. http://arxiv.org/abs/math/0605646.

[6] Bondy J A. Counting Subgraphs: A New Approach to the Caccetta-Haggkvist Conjecture [J]. Discrete Math, 1997, 165/166: 71-80.

[7] SHEN Jian. Directed Triangles in Digraphs [J]. J Combin Theory: Ser B, 1998, 74(2): 405-407.

[8] Hamburger P, Haxell P, Kostochka A. On Directed Triangles in Digraphs [J]. Electronic J Combin, 2007, 14(1): 19.