How Close to Regular Must a Multipartite Tournament Be to Secure a Given Path Covering Number?

Abstract

If $x$ is a vertex of a digraph $D$, then we denote by $d^{+}(x)$ and $d^{-}(x)$ the outdegree and the indegree of $x$, respectively. The global irregularity of a digraph $D$ is defined by $i_g(D)=max\{d^{+}(x),d^{-}(x)\}–min\{d^{+}(y),d^{-}(y)\}$ over all vertices $x$ and $y$ of $D$ (including $x=y$).

A $c$-partite tournament is an orientation of a complete $c$-partite graph. Recently, Volkmann and Winzen $[9]$ proved that $c$-partite tournaments with $i_g(D)=1$ and $c\ge 3$ or $i_g(D)=2$ and $c\ge 5$ contain a Hamiltonian path. Furthermore, they showed that these bounds are best possible.

Now, it is a natural question to generalize this problem by asking for the minimal value $g(i,k)$ with $i,k\ge 1$ arbitrary such that all $c$-partite tournaments $D$ with $i_g(D)\le i$ and $c\ge g(i,k)$ have a path covering number $pc(D)\le k$. In this paper, we will prove that $4i-4k\le g(i,k)\le 4i-3k-1$, when $i\ge k+2$. Especially in the case $k=1$, this yields that $g(i,1)=4i-4$, which means that all $c$-partite tournaments $D$ with the global irregularity $i_g(D)=i$ and $c\ge 4i-4$ contain a Hamiltonian path.