Turán Problems for k-Geodetic Digraphs

A digraph G is k-geodetic if for any pair of (not necessarily distinct) vertices u, v∈ V(G) there is at most one walk of length ≤ k from u to v in G. In this paper, we determine the largest possible size of a k-geodetic digraph with a given order. We then consider the more difficult problem of the largest size of a strongly-connected k-geodetic digraph with a given order, solving this problem for k= 2 and giving a construction which we conjecture to be extremal for larger k. We close with some results on generalised Turán problems for the number of directed cycles and paths in k-geodetic digraphs.