On the Path Covering Number of Given Subdigraphs of Regular Multipartite Tournaments

Abstract

A tournament is an orientation of a complete graph, and a multipartite or $c$-partite tournament is an orientation of a complete $c$-partite graph. If we speak of a path, then we mean a directed path.

Let $D$ be a regular $c$-partite tournament with $r$ vertices in each partite set, and let $X\subseteq V(D)$ be an arbitrary set with exactly $2$ vertices from each partite set. For all $c\ge 4$, the authors determined in a recent article the minimal value $g(c)$ such that $D–X$ is Hamiltonian for every regular multipartite tournament with $r\ge g(c)$. In this paper, we will supplement this result by postulating a given path covering number instead of the Hamiltonicity of the digraph $D–X$. This means, for all $c\ge 4$ and $k\ge 1$, we will determine the minimal value $h(k,c)$ such that $D–X$ can be covered by at most $k$ paths for every regular $c$-partite tournament with $r\ge h(k,c)$. Moreover, we will present the minimal path covering number of $D–X$, if $D$ is a regular $3$-partite tournament and $X$ contains exactly $s$ vertices ($s\ge 2$) from every partite set.