The minimum diameter of orientations of complete multipartite graphs

Abstract

Given a graph G, let script D sign(G) be the family of strong orientations of G, and define ε(G) = min{diamD\D ∈ script D sign(G)}. A pair {p, q} of integers is called a co-pair if 1 ≤, p ≤ q ≤ [[p/2] p]. A multiset {p, q, r} of positive integers is called a co-triple if {p, q} and {p, r} are co-pairs. Let K(p1,p2,...,pn) denote the complete n-partite graph having pi vertices in the ith partite set. In this paper, we show that if {p1,p2,...,pn} can be partitioned into co-pairs when n is even, and into co-pairs and a co-triple when n is odd, then ε(K(p1,p2,...,pn)) = 2 provided that (n, p1, p2, p3, p4) ≠ (4, 1, 1, 1, 1). This substantially extends a result of Gutin [3] and a result of Koh and Tan [4]. © Springer-Verlag 1996.