Note on the Path Covering Number of a Semicomplete Multipartite Digraph

Abstract

A digraph $D$ is called semicomplete $c$-partite if its vertex set $V(D)$ can be partitioned into $c$ sets (partite sets) such that for any two vertices $x$ and $y$ in different partite sets, at least one arc between $x$ and $y$ is in $D$ and there are no arcs between vertices in the same partite set. The path covering number of $D$ is the minimum number of paths in $D$ that are pairwise vertex disjoint and cover the vertices of $D$. Volkmann (1996) has proved two sufficient conditions on hamiltonian paths in semicomplete multipartite digraphs and conjectured two related sufficient conditions. In this paper, we derive sufficient conditions for a semicomplete multipartite digraph to have path covering number at most $k$ and show that Volkmann’s results and conjectures can be readily obtained from our conditions.