Longest cycles in almost regular 3-partite tournaments

AbstractIf D is a digraph, then we denote by V(D) its vertex set. A multipartite or c-partite tournament is an orientation of a complete c-partite graph. The global irregularity of a digraph D is defined byig(D)=max{max(d+(x),d-(x))-min(d+(y),d-(y))|x,y∈V(D)}.If ig(D)=0, then D is regular, and if ig(D)⩽1, then D is called almost regular. In 1997, Yeo has shown that each regular multipartite tournament is Hamiltonian. This remains valid for almost all almost regular c-partite tournaments with c≥4. However, there exist infinite families of almost regular 3-partite tournaments without any Hamiltonian cycle. In this paper we will prove that every vertex of an almost regular 3-partite tournament D is contained in a directed cycle of length at least |V(D)|-2. Examples will show that this result is best possible