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.

Résumé

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
Mots-clés : multipartite tournaments; regular multipartite tournaments; cycles