二部競賽圖中的最長圈問題

雷萬鵬， 劉凌晨， 韓 靜

（山西大學商務學院理學系，山西太原 030051）

0 引 言

文中所使用的術語和記號與文獻[1]一致。

設T（X，Y，A）為一個 p×q階二部競賽圖，（X，Y）是T（p，q）的一個劃分，令|X|=p，|Y|= q。分別用d+T（v）和d-T（v）表示v在圖T中的出度和入度。

如果T（p，q）滿足條件:uv?E且存在點w，使得uw∈E，wv∈E?d-（u）+d+（v）≥k，則稱T（p，q）滿足L（k）條件。

如果T（p，q）滿足條件:uv?E，d+（u）+ d-（v）≥k，則稱T（p，q）滿足O（k）條件。利用條件O（n）[2]，Jackson[3]證明了以下關于二部競賽圖中最長圈的問題。

定理1[3]如果T（p，q）滿足O（n）且強連通，則T包含一條長至少2n的圈。

進一步引入定義，設v∈V（T），S?V（T），定義

以及

對于所有x∈X1，y∈Y，若X1∈X，Y1∈Y，且xy∈A（T），則將其寫為 X1?Y1，反之亦然。如果X1={x}，那么可改為x?Y1。對于u，v∈V（T），u～v表明（u）=（v）且（u）=（v）。

1 主要結論

在證明結果以前先證明一個推論。

推論1 令C=v1v2…v2kv1為二部競賽圖T中一條最長圈，且P=u0u1…um為T-C中的一條路。

1）如果T是強連通的，那么T-C中無圈[4];

比C長，故矛盾。

則有vi-1u0，umvj+1∈A（T），不失一般性，假定j＞i。令

則vsu0，u0vs+2∈A（T）。進而由3）得到vs+1um∈A（T）。因此，很容易發現C′=v1…vi-1u0vs+2vjvi…vs+1umvj+1…v1是一個比C長的圈，矛盾。

證明5）:考察路P′=u0u1…um-1。因為m≥2且為偶數，那么m-1≥1且m-1為奇數，結合（um）?（um-1）和4），5）的結論成立。

利用這個等式和推論1中的2），得到

另一方面，我們觀察u0和um兩點。

情形1 假設m=1，則P=u0u1。我們知道u0u1?A（T），如果存在一個點w∈T滿足u1w∈A（T），wu0∈A（T）。則有（u1）+（u0）≥n。然而，我們知道如果u0u1∈A（T），那么u0，u1，不會同時屬于X或Y。不失一般性，我們假設u0∈X，u1∈Y。由上述假設有 u1w∈A（T），wu0∈A（T）。由此可見，w既不屬于X，又不屬于Y，這與T是一個二部競賽圖矛盾。故當m=1時，不存在w∈T，使得u1w∈A（T），wu0∈A（T），即m =1時，不滿足條件L（n）。

情形2 當m≥2時，可以發現 u0um?A（T），假設對于任一個m，都存在一個點，使其u0um滿足條件L（n），則得到

結合式（1）和式（2），解不等式得m≤2且|V（C）| =2n，即m=2。

當m=2時，P=u0u1u2，故至少存在一點u1，使其滿足條件L（n）。故只考慮當m=2時的情況即可。

論斷1[6-7]當viu0∈A（T）時，1≤i≤2n，u0?{vi-2，vi+2}。

即

論斷2[6]當u2vi∈A（T）時，1≤i≤2n，{vi-2，vi+2）?u2。

將每條弧的方向顛倒并結合論斷1很容易得到。

結合推論1中的3）以及論斷1和診斷2，可以得到結論，當n為偶數且不失一般性，將T中頂點以下列方式重排:

由推論1中的3）得到

論斷3

設圈

因此

另外，我們很容易發現對uK3∈K3有uK3～u2。故

定理證畢。

[1] J A Bondy，U S R Murty.Graph theory with applications[M].New York:Macmillan，1976.

[2] Wang Jianzhong.On arc even pancyclicty in diregular bipartite tournaments[J].Kexue Tongbao，1987，1:76.

[3] B Jackson.Long paths and cycles in oriented graphs [J].J.Graph Theory，1981，5（2）:149-157.

[4] Y Manoussakis.Extremal problems in directed graphs[D]:[Ph D Thesis].[S.l.]:University Parix-XI，1987.

[5] J Ayel.Degrees and longest paths in bipartite digraphs[J].Ann.Discrete Math.，1983，17:33-38.

[6] D Amar，Y Manoussakis.Cycles and paths of many lengths in bipartite digraphs[J].J.Combin.Theory Ser.B，1990，50:254-264.

[7] R Haggkvist，Y M anoussakis.Cycles and paths in bipartite tournaments with spanning configurations [J].Combinatiorica，1989，9（1）:51-56.