Three supplements to Reid's theorem in multipartite tournaments

An n-partite tournament is an orientation of a complete n-partite graph. In this paper, we give three supplements to Reid's theorem [K.B. Reid, Two complementary circuits in two-connected tournaments, Ann. Discrete Math. 27 (1985) 321-334] in multipartite tournaments. The first one is concerned with the lengths of cycles and states as follows: let D be an (alpha(D) + 1)-strong n-partite tournament with n >= 6, where alpha(D) is the independence number of D, then D contains two disjoint cycles of lengths 3 and n - 3, respectively, unless D is isomorphic to the 7-tournament containing no transitive 4-subtournament (denoted by T-7(1)). The second one is obtained by considering the number of partite sets that cycles pass through: every (alpha(D) + 1)-strong n-partite tournament D with n >= 6 contains two disjoint cycles which contain vertices from exactly 3 and n - 3 partite sets, respectively, unless it is isomorphic to T-7(1). The last one is about two disjoint cycles passing through all partite sets. (C) 2010 Published by Elsevier B.V.