Journal of the
Korean Mathematical Society
JKMS

ISSN(Print) 0304-9914 ISSN(Online) 2234-3008

Article

HOME ALL ARTICLES View

J. Korean Math. Soc. 2007; 44(3): 683-695

Printed May 1, 2007

Copyright © The Korean Mathematical Society.

Cycles through a given set of vertices in regular multipartite tournaments

Lutz Volkmann and Stefan Winzen

Abstract

A tournament is an orientation of a complete graph, and in general a multipartite or $c$-partite tournament is an orientation of a complete $c$-partite graph. In a recent article, the authors proved 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 exception of the case that $c = 4$ and $r = 2$. Here we will examine the existence of cycles with $r-2$ vertices from each partite set in regular multipartite tournaments where the $r-2$ vertices are chosen arbitrarily. Let $D$ be a regular $c$-partite tournament and let $X \subseteq V(D)$ be an arbitrary set with exactly $2$ vertices of each partite set. For all $c \ge 4$ we will determine the minimal value $g(c)$ such that $D-X$ is Hamiltonian for every regular multipartite tournament with $r \ge g(c)$.

Keywords: multipartite tournaments, regular multipartite tournaments, cycles through given set of vertices

MSC numbers: 05C20

Stats or Metrics

Share this article on :

Related articles in JKMS