The cycle structure of regular multipartite tournaments

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 (n greater than or equal to 3) tournament T is odd, then every arc of T is in a cycle that contains vertices from exactly m partite sets for all m is an element of { 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. (C) 2002 Elsevier Science B.V. All rights reserved.