Close to Regular Multipartite Tournaments Containing a Hamiltonian Path

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) \leq 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.