竞赛图中的反向泛圈弧

孟巍，李璐

（山西大学 数学科学学院，山西 太原 030006）

0 引言

本文所涉及的术语和符号参见文献［1］。在本文中只考虑简单有向图。设D是一个有向图，V(D)和A(D)分别表示图D的顶点集和弧集。定义|V(D)|为图D的顶点个数。设x，y∈V(D)，如果xy∈A(D)，则称x控制y且称y是x的一个外邻。一般来说，如果X和Y是图D的两个不相交的子图且X中的每个点都控制Y中的每个点，那么称X控制Y，记作X→Y。令W⊆V(D)，那么D W表示W在D中 的 诱 导 子 图 ，并 且D－W=D V(D)W。

在有向图中，路和圈总是有向的。弧uv的旁路是一条从u到v的路。长度为k的圈（或旁路）称为k-圈（或k-旁路）。称一个圈（或路）在有向图D中是哈密尔顿的，如果它包含D中所有顶点。在圈C上，从x到y的最短有向部分记为C[x，y]。

称有向图D中的弧uv是泛圈的，如果对每个3≤k≤|V(D)|，它都包含在一个长为k的圈中。称有向图D中的弧uv是一条k-反向弧，如果它有一条长为k－1 的旁路。如果对每个3≤k≤|V(D)|，弧uv在图D中都是k-反向弧，那么称弧uv是反向泛圈的。

称有向图D是强连通的，如果对于D中任意两个不同的顶点x和y，D中既包含从x到y的路，也包含从y到x的路。有向图D的强连通分支H是D的一个极大强连通子图。称D是k-强连通的，如果|V(D)|≥k+1 且对每个S⊆V(D)，D－S都是强连通的，其中|S|≤k－1。D的最小割是一个最小的顶点子集X使得D－X不强连通。

如果将有向图D中的每条弧xy替换成yx，则将得到的有向图称为D的逆，记作D－1。

竞赛图是无向完全图的定向图。对每个不强连通的竞赛图T，都存在唯一的分解T1，T2，…，Tα(α≥2)，满 足Ti→Tj对 每 个1≤i＜j≤α，称其为T的强连通分解。

关于竞赛图中的k-反向弧，Alspach，Reid 和Roselle 在文献［2］中证明了：顶点数n≥7 的正则竞赛图的每条弧都是k-反向弧，对每个k≥4。另外，文献［3］证明了：每条弧都在3 圈的3-强连通竞赛图中的每条弧都是k-反向弧，对每个k≥4，除非T同构于两个恰包含8 个顶点的特殊竞赛图。这一结果推广了文献［2］中的相应结果。

竞赛图的弧泛圈问题早已被许多数学家做了研究。文献［4］证明了正则竞赛图中的每条弧都是泛圈的；在文献［5］中，Moon 证明了每个强连通竞赛图至少包含三条泛圈弧，且刻画出达到这一下界的极图；更多的研究结果可参见文献［6-9］。近些年，关于竞赛图还有很多结果。本文研究了竞赛图反向泛圈弧，刻画出存在反向泛圈弧的竞赛图。

1 预备知识

下述著名的Camion 定理和引理对于证明主要结果是非常重要的。

定理1 （Camion）一个非平凡的竞赛图存在哈密尔顿圈当且仅当它是强连通的。

引理1 设T是一个不强连通的竞赛图，T1，T2，…，Tα(α≥2) 是T的强连通分解，那么每条从Ti到Tj的弧xy都有一条l-旁路，对每个1≤l≤p－1， 其 中 1≤i＜j≤α且p=|V(Ti)∪V(Ti+1)∪…∪V(Tj)|。

证明 根据定理1，每个强连通分支Tk要么是一个单点，要么包含一个哈密尔顿圈Ck，其中k=1，2，…，α。对于前者，仍然使用Ck来表示这个单点。依次沿着Ci，Ci+1，…，Cj延拓弧xy，可以得到弧xy的l-旁路，对每个1≤l≤p－1。■

引理2 每个非平凡的不强连通的竞赛图至少包含一条反向泛圈弧。

证明 设T是一个不强连通的竞赛图，T1，T2，…，Tα(α≥2)是T的强连通分解。根据引理1，从T1到Tα的每条弧在T中都是反向泛圈弧。■

下面考察图1 中的四个不包含反向泛圈弧的竞赛图。不难检验三个顶点的强连通竞赛图T3，四个顶点的强连通竞赛图T4以及中的每条弧都不是反向泛圈弧。图右下角的3-圈中每条弧都没有长为2 的旁路，其他弧都没有长为4 的旁路，因此，也不包含反向泛圈弧。

2 主要结果

本节将刻画至少存在一条反向泛圈弧的竞赛图。根据引理2，只需考虑非平凡的强连通竞赛图。

除特别声明外，以下均假设T是一个顶点数n≥6 的强连通竞赛图，并且设X是T的一个最小割 。 从 而 ，T－X有 强 分 解T1，T2，…，Tα(α≥2)，T X有强分解X1，X2，…，Xβ(β≥1)。

由引理3，只需考虑2≤α≤5 的情况。

下面假设|V(T1)|=1 且|V(T2)|≥3（另一种情况|V(T2)|=1 且|V(T1)|≥3 可以通过考察T－1类似地得到）。显然X→T1。

根据定理2，可以得到下面的结果。

推论1 每个顶点数至少为6 的竞赛图至少包含一条反向泛圈弧。