Digraphs that contain at most t distinct walks of a given length with the same endpoints

Let n, k, t be positive integers. What is the maximum number of arcs in a digraph on n vertices in which there are at most t distinct walks of length k with the same endpoints? Determine the extremal digraphs attaining the maximum number. When $$t=1$$ t = 1 , the problem has been studied by Wu, by Huang and Zhan, by Huang, Lyu and Qiao, by Lyu in four papers, and they solved all the cases but $$k=3$$ k = 3 . For $$t\ge 2$$ t ≥ 2 , Huang and Lyu proved that the maximum number is equal to $$n(n-1)/2$$ n ( n - 1 ) / 2 and the extremal digraph is the transitive tournament when $$n\ge 6t+2$$ n ≥ 6 t + 2 and $$k\ge n-1$$ k ≥ n - 1 . They also discussed the maximum number for the case $$n=k+2,k+3,k+4$$ n = k + 2 , k + 3 , k + 4 . In this paper, we solve the problem for the case $$k\ge 6t+1$$ k ≥ 6 t + 1 and $$n\ge k+5$$ n ≥ k + 5 , and we also characterize the structures of the extremal digraphs for $$n=k+2,k+3,k+4$$ n = k + 2 , k + 3 , k + 4 .