Weakly Complementary Cycles in 3-Connected Multipartite Tournaments
Weakly Complementary Cycles in 3-Connected Multipartite Tournaments
复制标题
DOI：
10.5666/kmj.2008.48.2.287
复制
发表时间：
2008-06
影响因子：
0.7
通讯作者：
L. Volkmann;Stefan Winzen
中科院分区：
文献类型：
--
作者：
L. Volkmann;Stefan Winzen
有向图 D 的顶点集用 V (D) 表示。 c 方锦标赛是完整 c 方图的一个方向。如果存在两个顶点不相交循环 C1 和 C2 使得 V (D) = V (C1) ( V (C2) ，则有向图 D 称为循环互补；如果存在两个顶点不相交循环 C1 和 C2 使得 V (C1) ( V (C2) 包含 D 的所有分集的顶点，则多部分锦标赛 D 称为弱循环互补。 Reid 完全解决了 2-连通锦标赛中的互补循环问题(4) 于 1985 年，Z. Song (5) 于 1993 年。他们证明了至少 8 个顶点上的每个 2-连通锦标赛 T 对于所有 3 • tjV (T)j=2 都具有长度为 t 和 jV (T)j i t 的互补循环。最近，Volkmann (8) 证明了阶数为 jV (D)j ‚ 8 的每个正则多方锦标赛 D 是循环互补的。在本文中，我们分析了多方。特别是，我们将用 c ‚ 3 来描述所有弱循环互补的 3 连通 c 部分锦标赛 1. 术语 在本文中，所有有向图都是无环和多弧的，有向图 D 的顶点集和弧集分别用 V (D) 和 E(D) 表示。支配 y，并且如果 X 和 Y 是 D 的两个不相交顶点集或子有向图，使得 X 的每个顶点支配 Y 的每个顶点，则我们说 X 支配 Y ，记为 X ! Y。此外，X ; Y 表示不存在从 Y 到 X 的弧。如果 D 是有向图，则顶点 x 的外邻域 N + D (x) = N + (x) 是以下集合：由 x 支配的顶点，并且邻域内 N i D (x) = N i (x) 是支配 x 的顶点集合，因此，如果弧 xy 2 E(D) 存在，则 y 是 x 的外部邻居，并且 x 是 y 的内部邻居。分别称为 x 的出度和入度 此外，数字 - + D = - + = minfd + (x)jx 2 V (D)g 和 - i D = - i = minfd i (x)jx 2 V (D)g 是最小出度和最小。
The vertex set of a digraph D is denoted by V (D). A c-partite tournament is an orientation of a complete c-partite graph. A digraph D is called cycle complementary if there exist two vertex disjoint cycles C1 and C2 such that V (D) = V (C1) ( V (C2), and a multipartite tournament D is called weakly cycle complementary if there exist two vertex disjoint cycles C1 and C2 such that V (C1) ( V (C2) contains vertices of all partite sets of D. The problem of complementary cycles in 2-connected tournaments was completely solved by Reid (4) in 1985 and Z. Song (5) in 1993. They proved that every 2-connected tournament T on at least 8 vertices has complementary cycles of length t and jV (T)j i t for all 3 • tjV (T)j=2. Recently, Volkmann (8) proved that each regular multipartite tournament D of order jV (D)j ‚ 8 is cycle complementary. In this article, we analyze multipartite tournaments that are weakly cycle complementary. Especially, we will characterize all 3-connected c-partite tournaments with c ‚ 3 that are weakly cycle complementary. 1. Terminology In this paper all digraphs are flnite without loops and multiple arcs. The vertex set and the arc set of a digraph D are denoted by V (D) and E(D), respectively. If xy is an arc of a digraph D, then we write x ! y and say x dominates y, and if X and Y are two disjoint vertex sets or subdigraphs of D such that every vertex of X dominates every vertex of Y , then we say that X dominates Y , denoted by X ! Y. Furthermore, X ; Y denotes the fact that there is no arc leading from Y to X. If D is a digraph, then the out-neighborhood N + D (x) = N + (x) of a vertex x is the set of vertices dominated by x and the in-neighborhood N i D (x) = N i (x) is the set of vertices dominating x. Therefore, if the arc xy 2 E(D) exists, then y is an outer neighbor of x and x is an inner neighbor of y. The numbers d + (x) = d + (x) = jN + (x)j and d i (x) = d i (x) = jN i (x)j are called the outdegree and the indegree of x, respectively. Furthermore, the numbers - + D = - + = minfd + (x)jx 2 V (D)g and - i D = - i = minfd i (x)jx 2 V (D)g are the minimum outdegree and the minimum