强连通多部竞赛图中顶点和弧的外路

郭巧萍

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

0 引言

竞赛图是有向图中最基本、结构最简单的一类有向图，多部竞赛图是竞赛图的自然推广，因此也是有向图中一个非常重要的图类，它于1968年在Moon的专著《Topics on Tourna⁃ments》中最早被提及［1］。1976年，Bondy最早对多部竞赛图中的圈进行了研究［2］。1995年，Gutin发表了第一篇关于多部竞赛图的综述文章［3］。随后，多部竞赛图被广泛关注，新的结果不断涌现。近年来，学者们从多个方面研究了多部竞赛图，可参见文章［4-12］。

路和圈一直是图中被研究的重要指标，1999年郭余宝在有向图中提出顶点和弧的外路的概念［8］，推广了有向图中的圈。外路是介于路和圈之间的一个概念，它的提出引起了学者们的兴趣。随后，多部竞赛图中的外路被研究，推广了竞赛图中圈方面的相关结果。

有向图中一个顶点x（或弧xy）的一条外路是指起始于x（或弧xy）的一条路，使得x控制这条路的终点仅当终点也控制x。一条长为k的外路称为k-外路。称顶点x（弧xy）是泛外路的，如果对每个k∈{3，4，…，|V(D)|}，D中都存在包含顶点x（弧xy）的(k−1)-外路。注意到，多部竞赛图中没有2圈，所以在多部竞赛图中，顶点x（或弧xy）的一条外路是起始于顶点x（或弧xy）的一条路且x不控制这条路的终点，即必有这条路的终点控制x或终点与x同部。显然，在竞赛图中，顶点x（或弧xy）属于一个k-圈当且仅当它有一条(k−1)-外路。

对于强连通多部竞赛图，郭余宝证明了下面的定理1。

定理1［8］若D是一个强连通c-部竞赛图，c≥3，则D的每个顶点都有(k−1)-外路，k∈{3，4，…，c}。

对于几乎正则多部竞赛图，下面两个定理被证明。

定理2［9］设D是几乎正则，但不正则的c-部（c≥8）竞赛图，每个部集至少包含两个点，则D中每条弧都存在(k−1)-外路，k∈{3，4，…，c}。

定理3［10］设 D 是几乎正则 c-部（c≥8）竞赛图，每个部集至少包含两个点，则D中每条弧 存 在 一 条 (k−1)-或 k-外 路 ，k ∈ {3，4，…，|V(D)|− 1}。

对于正则c-部竞赛图，郭余宝证明了下面的定理4。

定理4［8］一个正则 c-部（c≥3）竞赛图的每条弧都有一条(k−1)-外路，k∈{3，4，…，c}。

下面的定理5对定理4进行了推广。

定理5［11］一个正则 c-部（c≥5）竞赛图的每 条 弧 都 有 一 条 (k−1)-外 路 ，k∈{3，4，…，|V(D)|}。

定理6［12］一个 r-正则（r≥3）3-部竞赛图的每条弧都有一条2-，3-，5- 和6-外路。

在文献［12］中，弧不存在4-外路的r-正则（r≥2） 3-部竞赛图的结构也被完全刻画。

上面的结果中有一些外路的顶点数只达到了部集数，还未达到图的顶点数，有的只对顶点的外路做了讨论，也有的仅对弧的外路做了研究。本文中，利用在强连通多部竞赛图去顶点或去弧得到的有向图中找哈密尔顿圈的方法，进一步来寻求顶点和弧的外路，给出了顶点和弧泛外路的两个充分条件。具体地，首先证明了：设D是一个强连通c-部（c≥3）竞赛图，x是D中出度最小的顶点，若κ(D)≥α(D)+2，则对每个 k∈{3，4，…，|V(D)|}，x 的任意一条外弧都存在一条(k−1)-外路。作为推论，定理5中c≥6的情形很容易被证明。其次证明了：设D是一个几乎正则c-部（c≥6）竞赛图，每个部集至少包含3个顶点，则对每个k∈{3，4，…，|V(D)|}，D 中每个顶点都存在一条(k−1)-外路。

1 基本定义

本文使用的术语和符号参见文献［13］，所指的图都是没有重弧和环的有向图。设 D=(V(D)，A(D)) 是 一 个 有 向 图 ，一 个 由A⊆V(D)诱导的子图记作。如果xy是D中的一条弧，则称xy是x的一条外弧，也称x控制y，记作x→y。给定有向图D中的一个顶点x，所有控制x（被x控制）的顶点构成的集合记作N−D(x)（N+D(x)），称d+D(x)=|N+D(x)|和d−D(x)=|N−D(x)|分别为x在D中的出度和入度。在不致引起混淆的情况下，分别用N+(x)，N−(x)，d+(x)和d−(x)表示N+D(x)，N−D(x)，d+D(x)和d−D(x)。如果A和B是V(D)中两个互不相交的子集，使得A中的每个点控制B中的每个点，则称A控制B，记作A→B，否则称A不控制B。

设D是一个有向图，C=x1x2…xmx1是D中的一个圈，用x+i和x−i分别表示xi在圈C上的后继 和 前 驱 ，即 x+i=xi+1，x−i=xi−1。 特 别 地 ，对任意的正整数 l≥2，定义用表示不小于 α 的最小整数，表示不大于α的最大整数。

有向图D被称为是强连通的，如果对D中每对顶点x，y，都存在一条从x到y以及从y到x的有向路。称D是k-强连通的，如果|V(D)|≥k+1且 对 任 意 的 X⊆V(D)，且|X||S|的独立集S′。D的最大独立集的顶点数称为D的独立数，记为 α(D)。

有向图D中一个包含所有顶点的圈称为哈密尔顿圈。称D是哈密尔顿的，如果D中存在哈密尔顿圈。称弧xy是泛圈的，如果对每个k∈{3，4，…，|V(D)|}，D 中都存在包含弧 xy的k-圈。

2 强连通多部竞赛图中顶点和弧的外路

引理1［14］设D是一个强连通多部竞赛图，满足κ(D)≥α(D)，则D是哈密尔顿的。

引理2［15］每个正则竞赛图是弧泛圈的。

定理7 设D是一个n个顶点的强连通c-部 （c≥3） 竞赛图，x是D 中出度最小的顶点，若 κ(D)≥α(D)+2，则对每个 k∈{3，4，…，n}，x的任意一条外弧都存在一条(k−1)-外路。

证明 由题设，显然n≥4。对任意的xy∈A(D)，有 d+(x)≤d+(y)，且 κ(D−{x，y})≥κ(D)−2≥α(D)≥α(D−{x，y})。 由 引 理 1 得 ，D−{x，y}有 哈 密 尔 顿 圈 。 设 C=v1v2…vn−2v1是D−{x，y}的 一 个 哈 密 尔 顿 圈 ，令 N+(y)={v11，v12，…，v1r}。 对 于 任 意 k∈{3，4，…，n−1}，取 集 合， 则S≠N+(x)−{y}，否 则 d+(x)≥r+1>d+(y)，矛 盾 ！ 于 是 存 在 某 个但，则 x 不 控 制，且是xy的一条(k−1)-外路。

推论1 设D是一个n个顶点的强连通c-部（c≥3）竞赛图，x是D中出度最小的顶点，若κ(D)≥α(D)+2，则对每个k∈{3，4，…，n}，D 中都存在x的一条(k−1)-外路。

推论2 设D是一个n个顶点的正则c-部（c≥6）竞赛图，则D的每条弧都存在一条 (k−1)-外路，对每个 k∈{3，4，…，n}。

证明 由于D是正则的，所以D的每个部集所含顶点数相同。设D的每个部集都包含个顶点。当=1时，D是一个正则竞赛图，由引理2，D的每条弧是泛圈的，更有对每个k∈{3，4，…，n}，D的每条弧都存在一条(k−1)-外路。

又D是正则的，故D中所有点的出度相等，由定理7得，对每个k∈{3，4，…，n}，D中每条弧存在(k−1)-外路。

3 几乎正则多部竞赛图中顶点的外路

引理4［17］设D是一个强连通c-部竞赛图，且 V1，V2，…，Vc是 D 的 c 个 部 集 ，满 足 |V1|≤|V2|≤…≤|Vc|。il(D)是D的局部非正则度，如果

则D是哈密尔顿的。

引理5［9］设D是一个几乎正则c-部竞赛图，且 V1，V2，…，Vc是 D 的 c个部集，则对于所有的 i≤j，有||Vi|−|Vj| |≤2。

引理6［18］设 D 是一个有向图，X⊆V(D)且

定理8 设D是一个几乎正则c-部（c≥6）竞赛图，且D的每个部集至少包含两个顶点，则对任意的x∈V(D)，有D−{x}包含哈密尔顿圈。

证明 设 V1，V2，…，Vc是 D 的部集。由引理 5，可 设 2≤v*D=|V1|≤|V2|≤…≤|Vc|≤|V1|+2。令 D′=D−{x}。注意到 D′仍为 c-部 竞 赛 图 ，对 应 的 部 集 设 为 V1′，V2′，…，Vc′，则|Vc′|≤|V1|+2=v*D+2 且对所有的 1≤k≤c−1，有

由引理4得D′是哈密尔顿的，即D−{x}有哈密尔顿圈。

定理9 设D是一个n个顶点的几乎正则c-部（c≥6）竞赛图，且每个部集至少包含3个顶点，则对每个 k∈{3，4，…，n}，D 的每个顶点都存在一条(k−1)-外路。

证 明 设 V1，V2，…，Vc是 D 的 部 集 ，x∈V(D)是任意一个顶点，不妨设x∈V1，由定理8得D−{x}有哈密尔顿圈。设C=v1v2…vn−1v1是 D−{x}的 一 个 哈 密 尔 顿 圈 ，N+(x)={v11，v12，…，v1s}。 不 妨 设 v11，v12，…，v1s绕 C 的方向排序，对任意的 k∈{3，4，…，n}，取集 合如 果N+(x)=S，则 v11，v12，…，v1s在圈 C 上的间隔相等，设为 t，因而 t| (n−1)。设 n−1=ts，则显然 t≥2。

若 t=2，则 n−1=2s且 |N−(x)|+|V1|−1=(n−|N+(x)|)−1=n−s−1=(n−1)−s=s。

另一方面，因为D是几乎正则的，所以|N−(x)|≥s−1。又因为D的每个部集至少包含 3个 顶 点 ，故 |V1|−1≥2，则 |N−(x)|+|V1|−1≥s+1，矛盾！

若 t≥3， 则 |N−(x)|+|V1|−1=(n−|N+(x)|)−1=n−s−1=(n−1)−s=(t−1)s≥2s，故|N−(x)|+|V1|≥2s+1。又因为 D是几乎正则的，所以|N−(x)|≤s+1，故|V1|≥s。 由 引 理 5 得 对 所 有 的 i∈{2，3，…，c}，有|Vi|≥|V1|−2≥s−2。由于每个部集至少有3个 顶 点 ，所 以 2s+1≥|N+(x)|+|N−(x)|≥3(c−1)≥15，故 s≥7。

由D是几乎正则的，可知

与|N+(x)|=s矛盾！故N+(x)≠S，于是存在某 个 j∈{3，4，…，s}，使 得，即 x不控制。于是是x的一条(k−1)-外路。

4 结论

本文研究了强连通多部竞赛图中顶点和弧的外路，分别给出了强连通多部竞赛图中弧泛外路以及几乎正则多部竞赛图中顶点泛外路的一个充分条件。该结果丰富了前人的结果，然而目前已有的结果都集中在多部竞赛图中，对一般有向图中外路的研究还不够充分，今后可以进一步去研究一般有向图中的外路。