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

Title:

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

Creator:

Volkmann, Lutz and Winzen, Stefan

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:98730bf6-8289-4ba9-a7b0-1d3f77dd13a8
uuid:98730bf6-8289-4ba9-a7b0-1d3f77dd13a8

Subject:

multipartite tournaments, regular multipartite tournaments, and cycles

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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$.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

827-843

Source:

Czechoslovak Mathematical Journal | 2006 Volume:56 | Number:3

Harvested from:

CDK

Metadata only:

false