Extremal digraphs avoiding distinct walks of length 4 with the same endpoints (Q2151226)

For positive integers, \(n\) and \(k\), consider simple digraphs \(D\) of order \(n\) that do not contain two different walks of length \(k\) with the same initial vertex and the same terminal vertex. In 2007, \textit{X. Zhan} posed the problem of determining the maximal size of such digraphs and determining the structure of such digraphs with this maximal size; for more details [Matrix theory. Providence, RI: American Mathematical Society (AMS) (2013; Zbl 1275.15001)]. Both parts of the problem have since been solved for all \(k\neq 3,4\), and the maximal size has been found for \(k=4\); see [\textit{Z. Huang} et al., Discrete Math. 342, No. 6, 1703--1717 (2019; Zbl 1414.05133); \textit{Z. Huang} and \textit{X. Zhan}, ibid. 311, No. 1, 70--79 (2011; Zbl 1225.05115)]. The author of the present paper completes the solution to the problem for \(k=4\) and all \(n\geq k\) by finding the maximal-sized simple digraphs of order \(n\) containing no two walks of length \(4\) with the same initial and terminal vertices. For \(n\geq 12\), these are shown to be particularly nice and simple to describe: they are the balanced \(4\)-partite transitive tournaments. The author also poses the related problem: what is the maximal size of a simple digraph of order \(n\) that contains at least one walk of length \(k\) but does not contain two different walks of length \(k\) with the same initial vertex and the same terminal vertex. This problem is interesting because none of the extremal digraphs for Zhan's problem contain a walk of length \(k\) when \(n\) is large, at least for the so-far solved cases \(k\neq 3\).