Optimal strong (κ,d)-orientation of complete k-partite graphs

AbstractFor two vertices u and v in a strong oriented graph D, the strong distance sd(u,v) between u and v is the minimum size (the number of arcs) of a strong sub-digraph of D containing u and v. For a vertex v of D, the strong eccentricity se(v) is the strong distance between v and a vertex farthest from v. The strong diameter sdiam(D) is the maximum strong eccentricity among the vertices of D. The lower orientable strong diameter sdiam(G) of a graph G is the minimum strong diameter over all strong orientations of G. An orientation D of a graph G is said to be an optimal strong (κ,d)-orientation of G if κ(D)=⌊κ(G)/2⌋ and sdiam(D)=sdiam(G), where κ(D) (resp. κ(G)) is the strong connectivity of D (resp. connectivity of G). In this paper, we will show that each complete k-partite graph has an optimal strong (κ,d)-orientation