The minimum diameter of orientations of complete multipartite graphs

Given a graph G, let D(G) be the family of strong orientations of G, and define epsilon E(G) = min{diam D\D is an element of D(G)). A pair {p, q} of integers is called a co-pair if 1 less than or equal to p less than or equal to q less than or equal to [(p)([p/2])]. A multiset {p,q,r} of positive integers is called a co-triple if {p,q} and {p,r} are co-pairs. Let K(p(1),p(2),...,p(n)) denote the complete n-partite graph having p(i) vertices in the ith partite set. In this paper, we show that if {p(1),p(2),...,p(n)} can be partitioned into co-pairs when n is even, and into co-pairs and a co-triple when n is odd, then epsilon(K(p(1),p(2),...,p(n))) = 2 provided that (n,p(1),p(2),p(3),p(4)) not equal (4, 1, 1, 1, 1). This substantially extends a result of Gutin [3] and a result of Koh and Tan [4].