Three supplements to Reid’s theorem in multipartite tournaments

详细信息    查看全文

• 作者：Shengjia Li ; Wei Meng ; Yubao Guo
• 关键词：Multipartite tournaments ; Complementary cycles
• 刊名：Discrete Applied Mathematics
• 出版年：2010
• 出版时间：28 February 2010
• 年：2010
• 卷：158
• 期：4
• 页码：340-348
• 全文大小：661 K

文摘

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 (α(D)+1)-strong n-partite tournament with n≥6, where α(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 ). The second one is obtained by considering the number of partite sets that cycles pass through: every (α(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 . The last one is about two disjoint cycles passing through all partite sets.