Close to Regular Multipartite Tournaments Containing a Hamiltonian Path

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$). If $i_g(D)=0$, then $D$ is regular, and if $i_g(D)\le 1$, then $D$ is called almost regular. The local irregularity is defined as $i_l(D)=max[|d^{+}(x)–d^{-}(x)|]$ over all vertices $x$ of $D$. The path covering number of $D$ is the minimum number of directed paths in $D$ that are pairwise vertex disjoint and cover the vertices of $D$. A semicomplete $c$-partite digraph is a digraph obtained from a complete $c$-partite graph by replacing each edge with an arc, or a pair of mutually opposite arcs with the same end vertices. If a semicomplete $c$-partite digraph $D$ does not contain an oriented cycle of length two, then $D$ is called a $c$-partite tournament.
In 2000, Gutin and Yeo [7] proved sufficient conditions for the local irregularity of a semicomplete multipartite digraph to secure a path covering number of at most $k$. In this paper, we will give a useful supplement to this result by using bounds for the global irregularity that guarantee a path covering number of at most $k$. As an application, we will present sufficient conditions for close to regular multipartite tournaments containing a Hamiltonian path. Especially, we will characterize almost regular $c$-partite tournaments containing a Hamiltonian path.