On the connectivity of close to regular multipartite tournaments

AbstractIf 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 ig(D)=max{d+(x),d-(x)}-min{d+(y),d-(y)} over all vertices x and y of D (including x=y) and the local irregularity of a digraph D is il(D)=max|d+(x)-d-(x)| over all vertices x of D. Clearly, il(D)⩽ig(D). If ig(D)=0, then D is regular and if ig(D)⩽1, then D is almost regular.A c-partite tournament is an orientation of a complete c-partite graph. Let V1,V2,…,Vc be the partite sets of a c-partite tournament such that |V1|⩽|V2|⩽⋯⩽|Vc|. In 1998, Yeo provedκ(D)⩾|V(D)|-|Vc|-2il(D)3for each c-partite tournament D, where κ(D) is the connectivity of D. Using Yeo's proof, we will present the structure of those multipartite tournaments, which fulfill the last inequality with equality. These investigations yield the better boundκ(D)⩾|V(D)|-|Vc|-2il(D)+13in the case that |Vc| is odd. Especially, we obtain a 1980 result by Thomassen for tournaments of arbitrary (global) irregularity. Furthermore, we will give a shorter proof of the recent result of Volkmann thatκ(D)⩾|V(D)|-|Vc|+13for all regular multipartite tournaments with exception of a well-determined family of regular (3q+1)-partite tournaments. Finally we will characterize all almost regular tournaments with this property