1 Introduction

We discuss only finite simple digraphs (without multiple arcs but allowing loops). The terminology and notation is that of [1], except as indicated. The number of the vertices of a digraph is its order and the number of the arcs its size. We abbreviate directed walks and directed cycles as walks and cycles, respectively. The length of a walk or cycle is its number of arcs. A p-cycle is a cycle of length p. Similarly, a p-walk is a walk of length p.

Turán type problems are among the most important topics in graph theory, which concern the possible largest number of edges in graphs forbidding given subgraphs and the extremal graphs achieving that maximum number of edges. The systematic investigation of digraph extremal problem was initiated by Brown and Harary [2]. For more details, see [3, 4]. Given a family of digraphs \({\mathscr {F}}\), a digraph D is said to be \({\mathscr {F}}\)-free if D contains no subgraph from \({\mathscr {F}}\). Let \(ex(n,{\mathscr {F}})\) be the maximum size of \({\mathscr {F}}\)-free digraphs of order n and \(EX(n,{\mathscr {F}})\) be the set of \({\mathscr {F}}\)-free digraphs of order n with size \(ex(n,{\mathscr {F}})\). Given two positive integers k, t, denote by \({\mathscr {F}}_{k,t}\) the family of digraphs consisting of t different walks of length k with the same initial vertex and the same terminal vertex. For example, let \(x\rightarrow u_1\rightarrow u_2\rightarrow y\) and \(x\rightarrow v_1\rightarrow v_2\rightarrow y\) be two different walks (\(u_1=v_1\) and \(u_2=v_2\) do not hold simultaneously) with any pair of vertices may be the same. Then the union of these two walks belongs to \({\mathscr {F}}_{3,2}\). All the digraphs in \({\mathscr {F}}_{2,2}\) (or their inverses) are illustrated in Fig. 1.

Fig. 1
figure 1

The diagrams of the digraphs in \({\mathscr {F}}_{2,2}\)

Full size image

In [5], the authors studied the extremal digraphs such that for any pair of vertices x, y (not necessary different), there exist at most t directed walks of length k from x to y. It is equivalent to studying the Turán type problem as follows.

Problem 1

Given positive integers n, k, t, determine \(ex(n,{\mathscr {F}}_{k,t+1})\) and \(EX(n,{\mathscr {F}}_{k,t+1})\).

The initial version of Problem 1 was posed by Zhan at a seminar in 2007, which concerned the case \(t=1\); see [13, p. 234]. In the last decade, Problem 1 for the case \(t=1\) has been completely solved by the team work in [6,7,8, 11, 12].

For the general cases of Problem 1, the case \(k=2\) has been studied in [9]. Huang and Lyu [5] proved that given a positive integer t, the transitive tournament is the only extremal digraph when \(k\ge n-1\ge 6t+1\).

Theorem 2

([5]) Let t be a positive integer. For \(k\ge n-1\ge 6t+1\), a digraph \(D\in EX(n,{\mathscr {F}}_{k,t+1})\) if and only if D is a transitive tournament.

We define z(t) as the smallest integer such that if \(k\ge n-1\ge z(t)\), then \(D\in EX(n,{\mathscr {F}}_{k,t+1})\) if and only if D is a transitive tournament. Huang and Zhan [8] proved that \(z(1)=4\). It follows from Theorem 2 that z(t) is well defined for each positive integer t and

$$\begin{aligned} z(t)\le 6t+1. \end{aligned}$$

Based on this fact, using induction on n, Lyu [10] obtained the following result.

Theorem 3

Let k, n, t be positive integers with \(k\ge 6t+1\) and \(n\ge k+5+\lfloor \log _{2}(t)\rfloor \). Then \(D\in EX(n,{\mathscr {F}}_{k,t+1})\) if and only if D is an balanced blow-up of the transitive tournament of order k.

Motivated by Theorem 3, [11, Theorem 2] and [7, Theorem 1], we present a conjecture as follows.

Conjecture 4

Let k, t be positive integers with \(k\ge z(t)\) and let n be sufficiently large. Then \(D\in EX(n,{\mathscr {F}}_{k,t+1})\) if and only if D is a balanced blow-up of the transitive tournament of order k.

From [8] we get \(z(1)=4\). Hence, Conjecture 4 holds when \(t=1\). In view of this, it is important to determine the exact value or a better upper bound of z(t) for each t. Denote \(f(t)=\max \{2t+1,2\left\lceil \sqrt{2t+9/4}+1/2\right\rceil +3\}\). In this note, we present a new upper bound for z(t) as follows.

Theorem 5

Let t be a positive integer. Then

$$\begin{aligned} z(t)\le f(t). \end{aligned}$$
(1.1)

Adopting the same arguments as in the proofs in [10](modify a few details in the proof), we may obtain that Theorem 3 holds for \(k\ge f(t)\), which improves the main result of [10] when \(t\ge 2\).

2 Proof of Theorem 5

In order to present the proofs, we need the following notations and definitions. Let \(D=({\mathcal {V}},{\mathcal {A}})\) be a digraph with vertex set \({\mathcal {V}}\) and arc set \({\mathcal {A}}\). The size of D is denoted by a(D). The outdegree and indegree of a vertex u, denoted by \(d^+(u)\) and \(d^-(u)\), are the numbers of arcs with tails and heads u, respectively. Denote by

$$\begin{aligned} N^+(u)=\left\{ x\in {\mathcal {V}}|(u,x)\in {\mathcal {A}}\right\} \quad and \quad N^-(u)=\left\{ x\in {\mathcal {V}}|(x,u)\in {\mathcal {A}}\right\} . \end{aligned}$$

For a set \(X\subset {\mathcal {V}}\), we denote by D[X] the subgraph of D induced by X. For \(u,v\in {\mathcal {V}}\), uv denotes the arc from u to v and the notation \(u\rightarrow v\) means \(uv\in {\mathcal {A}}\).

Lemma 6

Let n, t be positive integers and let D be a digraph of order n. If an \(m_1\)-cycle \(C_{1}\) and an \(m_2\)-cycle \(C_{2}\) in D are joint, then D is not \({\mathscr {F}}_{k,t+1}\)-free for all \(k\ge L\lceil \log _{2}(t+1)\rceil ,\) where L is the least common multiple of \(m_1\) and \(m_2\).

Proof

Let \(a_1=L/m_1\) and \(a_2=L/m_2\). Assume \(C_{1}\) and \(C_{2}\) are joint at vertex v. We first consider the case \(k= L\lceil \log _{2}(t+1)\rceil \). Let w be the walk of length \(L\lceil \log _{2}(t+1)\rceil \) from v to v along \(C_1\). We partition w into \(\lceil \log _{2}(t+1)\rceil \) walks of the same length from v to v, say \(w_1,\ldots ,w_{\lceil \log _{2}(t+1)\rceil }\). Each of \(\{w_1,\ldots ,w_{\lceil \log _{2}(t+1)\rceil }\}\) could be replaced by repeating \(C_{2}\) \(a_2\) times. Therefore, there exist \(t+1\) distinct walks of length \(L\lceil \log _{2}(t+1)\rceil \) from v to v. For \(k> L\lceil \log _{2}(t+1)\rceil \), we can extend these walks along \(C_{2}\) to k-walks with the same endpoints. □

Lemma 7

([5]) Let n, t be positive integers and let D be a digraph of order n. If an \(m_1\)-cycle \(C_{1}\) and an \(m_2\)-cycle \(C_{2}\) in D are connected by an arc, then D is not \({\mathscr {F}}_{k,t+1}\)-free for \(k\ge t L+1.\)

The girth of a digraph D with a cycle is the length of its shortest cycle, denoted by g(D), and a digraph with no cycle has infinite girth.

Lemma 8

([5]) Let D be a loopless digraph of order n. If \(a(D)= n(n-1)/2\), then D is a transitive tournament or

$$\begin{aligned} g(D)\le 3. \end{aligned}$$

Let \(D=({\mathcal {V}},{\mathcal {A}})\) be a digraph with l loops. Denote by d(u) the number of arcs incident with u. We have

$$\begin{aligned} d(u)=\left\{ \begin{array}{ll} d^+(u)+d^-(u)-1,&{} if \, u\rightarrow u;\\ d^+(u)+d^-(u),&{}\text {otherwise}.\end{array}\right. \end{aligned}$$

Since \(a(D)=\sum \limits _{u\in {\mathcal {V}}}d^+(u)\) and \(a(D)=\sum \limits _{u\in {\mathcal {V}}}d^-(u)\), we have

$$\begin{aligned} 2a(D)=\sum \limits _{u\in {\mathcal {V}}}d(u)+l,\end{aligned}$$
(2.1)

and

$$\begin{aligned} d(u)=a(D)-a\left( D[{\mathcal {V}}\setminus \{u\}]\right) ~\text {for~all}~u\in {\mathcal {V}}. \end{aligned}$$

Lemma 9

Let \(D=({\mathcal {V}},{\mathcal {A}})\) be \({\mathscr {F}}_{k,t+1}\)-free with \(k\ge 2\lceil \log _2(t+1)\rceil \). Then \(d(u)\le |{\mathcal {V}}|\) for all \(u\in {\mathcal {V}}\).

Proof

Suppose there exists \(u\in {\mathcal {V}}\) such that \(d(u)\ge |{\mathcal {V}}|+1\). It follows that at least two cycles are joint at u. Moreover, these two cycles are either two 2-cycles or one loop and one 2-cycle. By Lemma 6, D is not \({\mathscr {F}}_{k,t+1}\)-free for \(k\ge 2\lceil \log _2(t+1)\rceil \), a contradiction. □

Lemma 10

Let \(D=({\mathcal {V}},{\mathcal {A}})\) be a digraph and let C and T be disjoint cycle and tournament in D, where \(|{\mathcal {V}}(T)|\ge 2\left\lceil \sqrt{2t+9/4}+1/2\right\rceil +1\). If there exists at least one arc between each vertex of \(C_1\) and each vertex of T, then D is not \({\mathscr {F}}_{k,t+1}\)-free for \(k\ge \max \{t+1,3\lceil \log _2(t+1)\rceil \}\).

Proof

To the contrary, suppose D is \({\mathscr {F}}_{k,t+1}\)-free for \(k\ge \max \{t+1,3\lceil \log _2(t+1)\rceil \}\). Suppose T contains a 3-cycle \(C_1\) as its subdigraph. Let

$$\begin{aligned} C\equiv w_1\rightarrow \dots \rightarrow w_l\rightarrow w_1 ~\text {and}~ C_1\equiv u_1\rightarrow u_2\rightarrow u_3\rightarrow u_1. \end{aligned}$$

Without loss of generality, we assume \(w_1\rightarrow u_1\). If \(u_2\rightarrow w_1\), we obtain a 3-cycle \(u_2\rightarrow w_1\rightarrow u_1\rightarrow u_2\). Since two 3-cycles are joint, by Lemma 6 we obtain D is not \({\mathscr {F}}_{k,t+1}\)-free, a contradiction. Hence, \(w_1\rightarrow u_2\). Similarly, \(w_1\rightarrow u_3\). If there exists some i such that \(u_i\rightarrow w_l\), we obtain \(u_i\rightarrow w_l\rightarrow w_1\rightarrow u_i\). Then two 3-cycles are joint. By Lemma 6, D is not \({\mathscr {F}}_{k,t+1}\)-free, a contradiction. Hence \(w_l\rightarrow u_i\) for \(i\in \{1,2,3\}\). Repeating the above arguments, we have

$$\begin{aligned} w_i\rightarrow u_j\quad \text {for}~ i\in \{1,2,\ldots ,l\} ~\text {and}~ j\in \{1,2,3\}. \end{aligned}$$
(2.2)

We construct walks of length k from \(w_1\) to \(u_1\) in the following way. For each \(t_1\in \{0,1,\ldots , t\}\), there are a walk of length \(t_1\) with its initial vertex \(w_1\) along C, say \(W_{t_1}\), and a walk of length \(k-t_1-1\) with terminal vertex \(u_1\) along \(C_1\), say \(W'_{t_1}\). Since (2.2), \(W_{t_1}W'_{t_1}\) is a walk of length k with initial vertex \(w_1\) and terminal vertex \(u_1\). Then there exist \(t+1\) distinct walks of length k from \(w_1\) to \(u_1\), a contradiction. Hence T contains no 3-cycles. Combining this with Lemma 8, T is acyclic, and hence it is transitive. Let \(a=\left\lceil \sqrt{2t+9/4}+1/2\right\rceil \). Since \(|{\mathcal {V}}(T)|\ge 2a+1\), without loss of generality, we assume \(w_1\) has at least \(a+1\) successors in T. Let those successors be \(\{t_0,t_1,t_2,\ldots ,t_a\}\) with \(t_i\rightarrow t_0\) for \(i=\{1,2,\ldots , a\}\). For any pair \(i,j\in \{1,2,\ldots , a\}\) with \(i<j\), we have \(\cdots \rightarrow w_1\rightarrow t_i\rightarrow t_j\rightarrow t_0\). Since \(a(a-1)/2\ge t+1\), there are more than t walks of length at least 3, a contradiction. □

Now we are ready to give the proof of Theorem 5.

Proof of Theorem 5

Assume \(k\ge n-1\ge f(t)\). It is sufficient to prove that \(D\in EX(n',{\mathscr {F}}_{k,t+1})\) if and only if D is a transitive tournament on n vertices. At first, we determine \(ex(n',{\mathscr {F}}_{k,t+1})\) for \(n'\ge a+2\), where \(a=2\left\lceil \sqrt{2t+9/4}+1/2\right\rceil +1\). It is easily seen that the transitive tournament of order \(n'\) is in \(EX(n',{\mathscr {F}}_{k,t+1})\). Hence,

$$\begin{aligned} ex\left( n',{\mathscr {F}}_{k,t+1}\right) \ge \frac{n'\left( n'-1\right) }{2} \end{aligned}$$
(2.3)

Now we prove that

$$\begin{aligned} ex\left( n',{\mathscr {F}}_{k,t+1}\right) = \frac{n'\left( n'-1\right) }{2}. \end{aligned}$$
(2.4)

Suppose otherwise that D is \({\mathscr {F}}_{k,t+1}\)-free on \(n'\) vertices with l loops and

$$\begin{aligned} a(D)\ge \frac{n'\left( n'-1\right) }{2}+1. \end{aligned}$$
(2.5)

By the pigeonhole principle, there exists some v such that \(d(v)\ge n'\). Combining this with Lemma 9, we have

$$\begin{aligned} d(v)= n'. \end{aligned}$$
(2.6)

We distinguish the following two cases.

Case 1. \(vv\notin {\mathcal {A}}\). Then there exists \(u\in {\mathcal {V}}\setminus \{v\}\) such that \(vu,uv\in {\mathcal {A}}\). By Lemma 6, two 2-cycles can not be joint. Hence v is on exactly one 2-cycle. Combining this with (2.6), each vertex in \({\mathcal {V}}\setminus \{u,v\}\) is jointed with v by exactly one arc. By Lemma 7, \(D-v\) has no 2-cycles or loops, which implies that \(d(w)\le n'-1\) for all \(w\in {\mathcal {V}}\setminus \{v,u\}\). By Lemma 9 and (2.5), we obtain \(d(u)=n'\) and

$$\begin{aligned} d(w)= n'-1\,\mathrm{for all}\, w\in {\mathcal {V}}\setminus \{v,u\}. \end{aligned}$$

Hence, \(D[{\mathcal {V}}\setminus \{u,v\}]\) is a tournament. Moreover, each vertex in \({\mathcal {V}}\setminus \{u,v\}\) is jointed with each of \(\{u,v\}\) by exactly one arc. Since \(|{\mathcal {V}}\setminus \{u,v\}|\ge a\), by Lemma 10, D is not \({\mathscr {F}}_{k,t+1}\), a contradiction.

Case 2. \(vv\in {\mathcal {A}}\). By Lemma 7, v is jointed by exactly one arc with each vertex in \({\mathcal {V}}\). Moreover, each vertex in \({\mathcal {V}}\setminus \{v\}\) is not on a loop or a 2-cycle. It follows from (2.5) and (2.6) that \(D[{\mathcal {V}}\setminus \{v\}]\) is a tournament. By Lemma 10, D is not \({\mathscr {F}}_{k,t+1}\)-free, a contradiction. Now we get (2.4).

Now we characterize the structures of the digraphs in \(EX(n,{\mathscr {F}}_{k,t+1})\). Let \(D\in EX(n,{\mathscr {F}}_{k,t+1})\). First we show that D contains no loops. Since \(n\ge a+2\), by (2.4), we obtain that

$$\begin{aligned} a(D)=\frac{n(n-1)}{2}~\text {and}~a\left( D\left[ {\mathcal {V}}\setminus \{u\}\right] \right) \le (n-1)(n-2)/2. \end{aligned}$$

Combining this with the definition of d(u), we get \(d(u)\ge n-1\) for all \(u\in {\mathcal {V}}\). Recalling (2.1), D is loopless. Moreover,

$$\begin{aligned} d(u)= n-1~\mathrm{for~ all~} u\in {\mathcal {V}}. \end{aligned}$$
(2.7)

Suppose D contains a 2-cycle \(u\rightarrow v\rightarrow u\). By Lemma 6, v can not be on two distinct 2-cycles. Hence, it is joined with \(n-2\) distinct vertices. Let \(v_0\in {\mathcal {V}}\) such that there is no arc between v and \(v_0\). From (2.7) \(v_0\) is on a 2-cycle, say \(v_0\rightarrow v_1\rightarrow v_0\). Obviously, \(v_1\) is joined with v. By Lemma 7, D is not \({\mathscr {F}}_{k,t+1}\)-free, a contradiction. Hence, D contains no 2-cycles. Recalling (2.7), D is a tournament.

Suppose D contains a 3-cycle \(u\rightarrow v\rightarrow w\rightarrow u\). Note that \(D[{\mathcal {V}}\setminus \{u,v,w\}]\) is also a tournament. Since \(n-3\ge a\), by Lemma 10, D is not \({\mathscr {F}}_{k,t+1}\)-free, a contradiction. It follows from Lemma 8 that D is a transitive tournament.

Conversely, it is easily seen that the transitive tournament of order n is in \(EX(n,{\mathscr {F}}_{k,t+1})\). This completes the proof. □

Remark that in the above proof, we also obtain \(ex(n,{\mathscr {F}}_{k,t+1})=n(n-1)/2\) for \(k\ge f(t)\) and \(2\left\lceil \sqrt{2t+9/4}+1/2\right\rceil +3\le n\le f(t)\). However, we do not know the structures of the digraphs attaining the maximum arcs.