Strong Distances in Strong Oriented Complete $k$-Partite Graphs

Abstract

For two vertices $u$ and $v$ in a strong oriented graph $D$, the strong distance $\mathrm{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 $\mathrm{se}(v)$ is the strong distance between $v$ and a vertex farthest from $v$. The strong radius $\mathrm{srad}(D)$ is the minimum strong eccentricity among the vertices of $D$. The strong diameter $\mathrm{sdiam}(D)$ is the maximum strong eccentricity among the vertices of $D$. In this paper, we investigate the strong distances in strong oriented complete $k$-partite graphs. For any integers $\delta ,r,d$ with $0\le \delta \le \lceil \frac{k}{2}\rceil ,3\le r\le \lfloor \frac{k}{2}\rfloor ,4\le d\le k$, we have shown that there are strong oriented complete $k$-partite graphs $K^{\prime },K”,K{”}^{\prime }$ such that $\mathrm{sdiam}(K^{\prime })–\mathrm{srad}(K^{\prime })=\delta ,\mathrm{srad}(K”)=r$, and $\mathrm{sdiam}(K{”}^{\prime })=d$.