Strong Distance in Strong Digraphs

Gary Chartrand1, David Erwin1, Michael Raines1, Ping Zhang 1
1Department of Mathematics and Statistics Western Michigan University Kalamazoo, MI 49008, USA

Abstract

For two vertices \(u\) and \(v\) in a strong oriented graph \(D\) of order \(n \geq 3\), the strong distance \(\text{sd}(u,v)\) between \(u\) and \(v\) is the minimum size of a strong subdigraph of \(D\) containing \(u\) and \(v\). For a vertex \(v\) of \(D\), the strong eccentricity \(\text{se}(v)\) is the strong distance between \(v\) and a vertex farthest from \(v\). The minimum strong eccentricity among the vertices of \(D\) is the strong radius \(\text{srad}(D)\), and the maximum strong eccentricity is its strong diameter \(\text{sdiam}(D)\). It is shown that every pair \(r,d\) of integers with \(3 \leq r \leq d \leq 2r\) is realizable as the strong radius and strong diameter of some strong oriented graph.
Moreover, for every strong oriented graph \(D\) of order \(n \geq 3\), it is shown that
\[
\text{sdiam}(D) \leq \left\lfloor \frac{5(n-1)}{3} \right\rfloor.
\]
Furthermore, for every integer \(n \geq 3\), there exists a strong oriented graph \(D\) of order \(n\) such that
\[
\text{sdiam}(D) = \left\lfloor \frac{5(n-1)}{3} \right\rfloor.
\]