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