Componentwise Complementary Cycles in Almost Regular 3-Partite Tournaments

摘要

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. Let V_1,V_2,...,V_c be the partite sets of D. If there exist two vertex disjoint cycles C and C′ in D such that V_i ∩ (V(C) U V(C′)) ≠ O for all i = 1, 2,..., c, then D is cycle componentwise complementary. The global irregularity of D is denned by i_g(D) = max{max(d~+(x),d~-(x)) -min(d~+(y),d~-(y))|x,y ∈ V(D)} over all vertices x and y of D (x = y is admissible), where d~+(x) and d~-(x) are the outdegree and indegree of x, respectively. If i_g(D) ≤ 1, then D is almost regular. In this paper, we consider a special kind of multipartite tournaments which are almost regular 3-partite tournaments, and we show that each almost regular 3-partite tournament D is cycle componentwise complementary, unless D is isomorphic to D_(3,2).