Partitioning a Strong Tournament into $k$ Cycles

Abstract

A digraph $T$ is called strongly connected if for every pair of vertices $u$ and $v$ there exists a directed path from $u$ to $v$ and a directed path from $v$ to $u$. Denote the in-degree and out-degree of a vertex $v$ of $T$ by $d^{-}(v)$ and $d^{+}(v)$, respectively. We define ${\delta }^{-}=\underset{v\in V(T)}{min}\{d^{-}(v)\}$, and ${\delta }_{+}=\underset{v\in V(T)}{min}\{d^{+}(v)\}$. Let $T_0$ be a $7$-tournament which contains no transitive $4$-subtournament. Let $T$ be a strong tournament, $T≆T_0$ and $k\ge 2$. In this paper, we show that if ${\delta }^{+}+{\delta }^{-}\ge \frac{k-2}{k-1}n+3k(k-1)$, then $T$ can be partitioned into $k$ cycles. When $n\ge 3k(k-1)$ a regular strong $n$-tournament can be partitioned into $k$ cycles and a almost regular strong $n$-tournament can be partitioned into $k$ cycles when $n\ge (3k+1)(k-1)$. Finally, if a strong tournament $T$ can be partitioned into $k$ cycles, $q$ is an arbitrary positive integer not larger than $k$. We prove that $T$ can be partitioned into $q$ cycles.