Strong Distances in Strong Oriented Complete \(k\)-Partite Graphs

Huifang Miao1, Xiaofeng Guo2
1School of Energy Research, Xiamen University, Xiamen Fujian 361005, P. R. China
2School of Mathematical Sciences, Xiamen University, Xiamen Fujian 361005, P. R. China

Abstract

For two vertices \(u\) and \(v\) in a strong oriented graph \(D\), the strong distance \(\operatorname{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 \(\operatorname{se}(v)\) is the strong distance between \(v\) and a vertex farthest from \(v\). The strong radius \(\operatorname{srad}(D)\) is the minimum strong eccentricity among the vertices of \(D\). The strong diameter \(\operatorname{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 \leq \delta \leq \lceil\frac{k}{2}\rceil, 3 \leq r \leq \lfloor\frac{k}{2}\rfloor, 4 \leq d \leq k\), we have shown that there are strong oriented complete \(k\)-partite graphs \(K’, K”, K”’\) such that \(\operatorname{sdiam}(K’) – \operatorname{srad}(K’) = \delta, \operatorname{srad}(K”) = r\), and \(\operatorname{sdiam}(K”’) = d\).