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^- = \min_{v\in V(T)} \{d^-(v)\}\), and \(\delta_+ = \min_{v\in V(T)} \{d^+(v)\}\). Let \(T_0\) be a \(7\)-tournament which contains no transitive \(4\)-subtournament. Let \(T\) be a strong tournament, \(T \ncong T_0\) and \(k \geq 2\). In this paper, we show that if \(\delta^+ + \delta^- \geq \frac{k-2}{k-1}n+3k(k-1)\), then \(T\) can be partitioned into \(k\) cycles. When \(n \geq 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 \geq (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.