On the order and size of \(s\)-geodetic digraphs with given connectivity
A digraph \(G\) without cycles of length at most \(s\) is said to be \(s\)-geodetic if for any two different vertices \(x,y\), there is at most one \(x\)--\(y\) path of length not exceeding \(s\). The authors are interested in the maximum integer \(s\) for which \(G\) is \(s\)-geodetic. Some recent results [see, e.g., \textit{M. A. Fiol}, J. Graph Theory 17, 31-45 (1993; Zbl 0783.05054)] show that if the order \(n\) of a digraph is big enough, then its connectivity \(\kappa\) attains its maximum value. In this paper several such results are derived for \(s\)-geodetic digraphs of a small order. E.g., for \(s\geq 2\), if the minimum degree \(\delta \geq \lceil \root s \of {\frac n2 - 1}\rceil\), then \(\kappa = \delta\). Similar results are given also for the edge-connectivity, superconnectivity and edge-superconnectivity.
scientific article; zbMATH DE number 1110072