Cycles with a given number of vertices from each partite set in regular multipartite tournaments

Volkmann, Lutz ; Winzen, Stefan

Czechoslovak Mathematical Journal, Tome 56 (2006) no. 3, pp. 827-843

Abstract (VO)

If $x$ is a vertex of a digraph $D$, then we denote by $d^+(x)$ and $d^-(x)$ the outdegree and the indegree of $x$, respectively. A digraph $D$ is called regular, if there is a number $p \in \mathbb{N}$ such that $d^+(x) = d^-(x) = p$ for all vertices $x$ of $D$. A $c$-partite tournament is an orientation of a complete $c$-partite graph. There are many results about directed cycles of a given length or of directed cycles with vertices from a given number of partite sets. The idea is now to combine the two properties. In this article, we examine in particular, whether $c$-partite tournaments with $r$ vertices in each partite set contain a cycle with exactly $r-1$ vertices of every partite set. In 1982, Beineke and Little [2] solved this problem for the regular case if $c = 2$. If $c \ge 3$, then we will show that a regular $c$-partite tournament with $r \ge 2$ vertices in each partite set contains a cycle with exactly $r-1$ vertices from each partite set, with the exception of the case that $c = 4$ and $r = 2$.

Détail

Classification : 05C20, 05C38, 05C40
Keywords: multipartite tournaments; regular multipartite tournaments; cycles