Three supplements to Reids theorem in multipartite tournaments
An n n -partite tournament is an orientation of a complete n n -partite graph. In this paper, we give three supplements to Reids theorem [K.B. Reid, Two complementary circuits in two-connected tournaments, Ann. Discrete Math. 27 (1985) 321334] in multipartite tournaments. The first one is concerned with the lengths of cycles and states as follows: let D D be an (?(D)+1 ? ( D ) + 1 )-strong n n -partite tournament with n?6 n ? 6 , where ?(D) ? ( D ) is the independence number of D D , then D D contains two disjoint cycles of lengths 3 and n?3 n ? 3 , respectively, unless D 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 (?(D)+1 ? ( D ) + 1 )-strong n n -partite tournament D D with n?6 n ? 6 contains two disjoint cycles which contain vertices from exactly 3 and n?3 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.
multipartite tournaments complementary cycles