The minimum diameter of orientations of complete multipartite graphs (Q2563422)

A pair of integers \(\{p, q\}\) is called a co-pair if \(1\leq p\leq q\leq{p\choose \lfloor p/2\rfloor}\). A multiset \(\{p, q, r\}\) is a co-triple if both \(\{p, q\}\) and \(\{p, r\}\) are co-pairs. \(K(p_1,\dots,p_n)\) stands for complete \(n\)-partite graph with \(p_i\) vertices in the \(i\)th partite set. The authors prove that if \(\{p_1,\dots,p_n\}\) can be partitioned into co-pairs or into co-pairs and a co-triple, then there exists an orientation of \(K(p_1,\dots,p_n)\) of diameter two provided that \((n,p_1,p_2,p_3,p_4)\neq(4,1,1,1,1)\). This generalizes a result obtained by \textit{J. Plesník} [Acta Math. Univ. Comenianae 46/47, 225-236 (1985; Zbl 0613.05024)], \textit{G. Gutin} [Graphs Comb. 10, No. 3, 225-230 (1994; Zbl 0814.05044)], and the authors [Discrete Math. 149, No. 1-3, 131-139 (1996; Zbl 0846.05038)].