The cycle structure of regular multipartite tournaments |
| |
Authors: | Yubao Guo Jin Ho Kwak |
| |
Affiliation: | a Lehrstuhl C für Mathematik, RWTH Aachen, Templergraben 55, D-52056, Aachen, Germany b Department of Mathematics, Pohang University of Science and Technology, Pohang 790-784, North Korea |
| |
Abstract: | A multipartite tournament is an orientation of a complete multipartite graph. A tournament is a multipartite tournament, each partite set of which contains exactly one vertex. Alspach (Canad. Math. Bull. 10 (1967) 283) proved that every regular tournament is arc-pancyclic. Although all partite sets of a regular multipartite tournament have the same cardinality, Alspach's theorem is not valid for regular multipartite tournaments. In this paper, we prove that if the cardinality common to all partite sets of a regular n-partite (n3) tournament T is odd, then every arc of T is in a cycle that contains vertices from exactly m partite sets for all m{3,4,…,n}. This result extends Alspach's theorem for regular tournaments to regular multipartite tournaments. We also examine the structure of cycles through arcs in regular multipartite tournaments. |
| |
Keywords: | Cycle Regularity Multipartite tournament |
本文献已被 ScienceDirect 等数据库收录! |
|