孟巍，李璐

（山西大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006）

0 引言

本文所涉及的術(shù)語(yǔ)和符號(hào)參見(jiàn)文獻(xiàn)［1］。在本文中只考慮簡(jiǎn)單有向圖。設(shè)D是一個(gè)有向圖，V(D)和A(D)分別表示圖D的頂點(diǎn)集和弧集。定義|V(D)|為圖D的頂點(diǎn)個(gè)數(shù)。設(shè)x，y∈V(D)，如果xy∈A(D)，則稱x控制y且稱y是x的一個(gè)外鄰。一般來(lái)說(shuō)，如果X和Y是圖D的兩個(gè)不相交的子圖且X中的每個(gè)點(diǎn)都控制Y中的每個(gè)點(diǎn)，那么稱X控制Y，記作X→Y。令W?V(D)，那么D W表示W(wǎng)在D中 的 誘 導(dǎo) 子 圖 ，并 且D－W=D V(D)W。

在有向圖中，路和圈總是有向的。弧uv的旁路是一條從u到v的路。長(zhǎng)度為k的圈（或旁路）稱為k-圈（或k-旁路）。稱一個(gè)圈（或路）在有向圖D中是哈密爾頓的，如果它包含D中所有頂點(diǎn)。在圈C上，從x到y(tǒng)的最短有向部分記為C[x，y]。

稱有向圖D中的弧uv是泛圈的，如果對(duì)每個(gè)3≤k≤|V(D)|，它都包含在一個(gè)長(zhǎng)為k的圈中。稱有向圖D中的弧uv是一條k-反向弧，如果它有一條長(zhǎng)為k－1 的旁路。如果對(duì)每個(gè)3≤k≤|V(D)|，弧uv在圖D中都是k-反向弧，那么稱弧uv是反向泛圈的。

稱有向圖D是強(qiáng)連通的，如果對(duì)于D中任意兩個(gè)不同的頂點(diǎn)x和y，D中既包含從x到y(tǒng)的路，也包含從y到x的路。有向圖D的強(qiáng)連通分支H是D的一個(gè)極大強(qiáng)連通子圖。稱D是k-強(qiáng)連通的，如果|V(D)|≥k+1 且對(duì)每個(gè)S?V(D)，D－S都是強(qiáng)連通的，其中|S|≤k－1。D的最小割是一個(gè)最小的頂點(diǎn)子集X使得D－X不強(qiáng)連通。

如果將有向圖D中的每條弧xy替換成yx，則將得到的有向圖稱為D的逆，記作D－1。

競(jìng)賽圖是無(wú)向完全圖的定向圖。對(duì)每個(gè)不強(qiáng)連通的競(jìng)賽圖T，都存在唯一的分解T1，T2，…，Tα(α≥2)，滿 足Ti→Tj對(duì) 每 個(gè)1≤i＜j≤α，稱其為T的強(qiáng)連通分解。

關(guān)于競(jìng)賽圖中的k-反向弧，Alspach，Reid 和Roselle 在文獻(xiàn)［2］中證明了：頂點(diǎn)數(shù)n≥7 的正則競(jìng)賽圖的每條弧都是k-反向弧，對(duì)每個(gè)k≥4。另外，文獻(xiàn)［3］證明了：每條弧都在3 圈的3-強(qiáng)連通競(jìng)賽圖中的每條弧都是k-反向弧，對(duì)每個(gè)k≥4，除非T同構(gòu)于兩個(gè)恰包含8 個(gè)頂點(diǎn)的特殊競(jìng)賽圖。這一結(jié)果推廣了文獻(xiàn)［2］中的相應(yīng)結(jié)果。

競(jìng)賽圖的弧泛圈問(wèn)題早已被許多數(shù)學(xué)家做了研究。文獻(xiàn)［4］證明了正則競(jìng)賽圖中的每條弧都是泛圈的；在文獻(xiàn)［5］中，Moon 證明了每個(gè)強(qiáng)連通競(jìng)賽圖至少包含三條泛圈弧，且刻畫出達(dá)到這一下界的極圖；更多的研究結(jié)果可參見(jiàn)文獻(xiàn)［6-9］。近些年，關(guān)于競(jìng)賽圖還有很多結(jié)果。本文研究了競(jìng)賽圖反向泛圈弧，刻畫出存在反向泛圈弧的競(jìng)賽圖。

1 預(yù)備知識(shí)

下述著名的Camion 定理和引理對(duì)于證明主要結(jié)果是非常重要的。

定理1 （Camion）一個(gè)非平凡的競(jìng)賽圖存在哈密爾頓圈當(dāng)且僅當(dāng)它是強(qiáng)連通的。

引理1 設(shè)T是一個(gè)不強(qiáng)連通的競(jìng)賽圖，T1，T2，…，Tα(α≥2) 是T的強(qiáng)連通分解，那么每條從Ti到Tj的弧xy都有一條l-旁路，對(duì)每個(gè)1≤l≤p－1， 其 中 1≤i＜j≤α且p=|V(Ti)∪V(Ti+1)∪…∪V(Tj)|。

證明 根據(jù)定理1，每個(gè)強(qiáng)連通分支Tk要么是一個(gè)單點(diǎn)，要么包含一個(gè)哈密爾頓圈Ck，其中k=1，2，…，α。對(duì)于前者，仍然使用Ck來(lái)表示這個(gè)單點(diǎn)。依次沿著Ci，Ci+1，…，Cj延拓弧xy，可以得到弧xy的l-旁路，對(duì)每個(gè)1≤l≤p－1?！?/p>

引理2 每個(gè)非平凡的不強(qiáng)連通的競(jìng)賽圖至少包含一條反向泛圈弧。

證明 設(shè)T是一個(gè)不強(qiáng)連通的競(jìng)賽圖，T1，T2，…，Tα(α≥2)是T的強(qiáng)連通分解。根據(jù)引理1，從T1到Tα的每條弧在T中都是反向泛圈弧。■

下面考察圖1 中的四個(gè)不包含反向泛圈弧的競(jìng)賽圖。不難檢驗(yàn)三個(gè)頂點(diǎn)的強(qiáng)連通競(jìng)賽圖T3，四個(gè)頂點(diǎn)的強(qiáng)連通競(jìng)賽圖T4以及中的每條弧都不是反向泛圈弧。圖右下角的3-圈中每條弧都沒(méi)有長(zhǎng)為2 的旁路，其他弧都沒(méi)有長(zhǎng)為4 的旁路，因此，也不包含反向泛圈弧。

2 主要結(jié)果

本節(jié)將刻畫至少存在一條反向泛圈弧的競(jìng)賽圖。根據(jù)引理2，只需考慮非平凡的強(qiáng)連通競(jìng)賽圖。

除特別聲明外，以下均假設(shè)T是一個(gè)頂點(diǎn)數(shù)n≥6 的強(qiáng)連通競(jìng)賽圖，并且設(shè)X是T的一個(gè)最小割 。 從 而 ，T－X有 強(qiáng) 分 解T1，T2，…，Tα(α≥2)，T X有強(qiáng)分解X1，X2，…，Xβ(β≥1)。

由引理3，只需考慮2≤α≤5 的情況。

下面假設(shè)|V(T1)|=1 且|V(T2)|≥3（另一種情況|V(T2)|=1 且|V(T1)|≥3 可以通過(guò)考察T－1類似地得到）。顯然X→T1。

根據(jù)定理2，可以得到下面的結(jié)果。

推論1 每個(gè)頂點(diǎn)數(shù)至少為6 的競(jìng)賽圖至少包含一條反向泛圈弧。