Huifang Miao

For 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 defined by optimal strong $(\kappa, d)$-orientation of $G$ if and only if $\kappa(D)=\lfloor\kappa(G)/2\rfloor$ and $sdiam(D)=sdiam(G)$. In this paper, we will show that each complete $k$-partite graph has an optimal strong $(\kappa, d)$-orientation.