The minimum diameter of orientations of complete multipartite graphs

Given a graphG, letB be the family of strong orientations ofG, and define A pair {p,q} of integers is called aco-pair if 1 p q . A multiset {p, q, r} of positive integers is called aco-triple if {p, q} and {p, r} are co-pairs. LetK(p₁, p₂,..., p_n) denote the completen-partite graph havingp _i vertices in theith partite set.In this paper, we show that if {p ₁, p₂,...,p_n} can be partitioned into co-pairs whenn is even, and into co-pairs and a co-triple whenn is odd, then(K(p₁, p₂,..., p_n)) = 2 provided that (n,p ₁, p₂, p₃, p₄) (4, 1, 1, 1, 1). This substantially extends a result of Gutin 3] and a result of Koh and Tan 4].