孟巍，李璐

（山西大学 数学科学学院，山西 太原 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。……