# The Turán problems of directed paths and cycles in digraphs ††thanks:
Supported by NSFC (Nos. 12071370, 11871311, 11631014).

Wenling Zhou School of Mathematics, Shandong University, Jinan 250100, P.R.
China. Email<EMAIL_ADDRESS>Binlong Li Corresponding author.
School of Mathematics and Statistics, Northwestern Polytechnical University,
Xi’an 710072, P.R. China. Email<EMAIL_ADDRESS>
Abstract: Let $\overrightarrow{P_{k}}$ and $\overrightarrow{C_{k}}$ denote the
directed path and the directed cycle of order $k$, respectively. In this
paper, we determine the precise maximum size of $\overrightarrow{P_{k}}$-free
digraphs of order $n$ as well as the extremal digraphs attaining the maximum
size for large $n$. For all $n$, we also determine the precise maximum size of
$\overrightarrow{C_{k}}$-free digraphs of order $n$ as well as the extremal
digraphs attaining the maximum size. In addition, Huang and Lyu [Discrete
Math. 343(5) 2020] characterized the extremal digraphs avoiding an orientation
of $C_{4}$. For all other orientations of $C_{4}$, we also study the maximum
size and the extremal digraphs avoiding them.

Keywords: Turán number, directed path, directed cycle, extremal digraph

##  1 Introduction

The Turán problem is a classic extremal problem in graph theory, whose origin
can be traced back to Turán’s generalization of Mantel’s theorem [24]. How
many edges guarantee that a graph on $n$ vertices has a complete subgraph with
$k$ vertices, no matter how these edges are arranged? The answer is given by
Turán’s theorem [29] in 1941. Turán’s theorem is not merely one extremal
result among others, but also initiated extremal graph theory. In general, for
a given graph (or digraph) $H$, a graph (or digraph) is called $H$-free if it
contains no $H$ as a subgraph (or subdigraph). An $H$-free graph (or digraph)
on $n$ vertices with the maximum possible number of edges (or arcs) is called
extremal for $H$ and $n$; its number of edges (or arcs) is denoted by ${\rm
ex}(n,H)$. This quantity is referred to as the Turán number for $H$ and $n$.
Sometimes, the $H$-free extremal graphs may be not unique, we define ${\rm
EX}(n,H)$ to be the family of all $H$-free extremal graphs (or digraphs). The
Turán problem focuses on the Turán number and the extremal graphs (or
digraphs) for given $H$. Most results on classical Turán problem have been
obtained for undirected graphs, see [3, 9, 11, 28, 22]. Relatively few results
for directed graphs have been obtained, see [4, 5, 6, 20, 21]. In this paper,
we are interested in the Turán problem for directed paths and directed cycles.

The Turán problem of complete digraphs and tournaments has been solved in work
of Brown and Harary [5], and the extremal digraphs have a interestingly
counterpart to the extremal graphs for complete graphs (see in [5]). They also
studied the Turán problem of some digraphs on at most $4$ vertices where any
two vertices are joined by at least one arc. The study of paths and cycles are
also the focus of the Turán problem. Erdős and Gallai [12] determined the
Turán number of paths. Later, Faudree and Schelp [14] gave a completely
characterization of the extremal graphs for paths. However, it is very
difficult to determine the exact Turán number of the even cycles; see [1, 7,
15, 23, 26]. Even for $C_{4}$ (the cycle of order 4), we only know some
asymptotic results. Therefore, it is interesting to study the Turán problem of
a specific orientation of paths (or cycles). Among all the orientations of
paths (or cycles), the directed path (or directed cycle) is one of the most
natural orientation. In [17, 18], Howalla et al. determined the maximum size
of the digraphs without 2-cycles and avoiding $k$ directed paths with the same
initial vertex and terminal vertex for $k=2,3$. By using matrices, Huang and
Lyu [19] studied the Turán problem of a specific orientation of $C_{4}$,
denoted by $\overrightarrow{P_{2,2}}$, which consists of two paths of order 3
with the same initial and terminal vertices.

Inspired by the studied of Brown-Harary and Huang-Lyu, we naturally want to
know if there are interesting relationships between the extremal structures of
directed paths (or directed cycles) and the extremal structures of paths and
cycles. In addition, a natural important question: is there a kind of
orientation of $C_{4}$ such that the Turán number is hard as difficult to
calculate as $C_{4}$? In this paper, we will answer these questions and shed
light on the relationship of extremal structures between graphs and digraphs.

###  1.1 Preliminaries

In order to present our results, we begin with some notation. We also
introduce some classical results that will be used in the proofs.

To avoid confusion, we first distinguish some notation between graphs and
digraphs. A (simple) graph, is a pair $G=(V(G),E(G))$, where $V(G)$ is a non-
empty finite vertex set and $E(G)$, a set of $2$-element subsets of $V(G)$ is
an edge set. A directed graph, digraph for short, is a pair $D=(V(D),A(D))$,
where $V(D)$ is also a vertex set, but $A(D)$ is a set of order pairs of
vertices, called arc (or directed edge) set. The cardinality of $E(G)$ and
$A(D)$ is denoted by $e(G)$ and $a(D)$, respectively. An edge (or arc) with
identical ends is called a loop. Two or more edges with the same pair of ends
are said to be parallel edges. If two arcs between a pair of vertices have the
same direction, we say they are parallel. In this paper, our notation depends
heavily on the use of letters $G$ for graphs and $D$ for digraphs, and graphs
and digraphs are strict, i.e., they do not allow loops and parallel edges
(arcs). If a graph contains parallel edges, then we call it a multigraph.
Multigraphs in this paper have maximum edge-multiplicity $2$. In particular,
we say that $G$ (or $D$) is complete if $E(G)=\\{\\{u,v\\}:u,v\in V(G),u\neq
v\\}$ (or $A(D)=\\{(u,v):u,v\in V(D),u\neq v\\}$). We denote by $K_{k}$ (or
$\overleftrightarrow{K_{k}}$) the complete graph (or complete digraph) with
$k$ vertices. A subset of $V(G)$ (or $V(D)$) is independent in $G$ (or $D$) if
no two of its vertices are connected by an edge (or arc).

An orientation of a graph (or multigraph) $G$ is a digraph obtained from $G$
by assigning a direction to each edge of $G$. In this paper, the orientations
of multigraphs are strict, i.e., they have no parallel arcs. In general, an
orientation of a complete graph $K_{k}$ is called a tournament, denoted by
$\overrightarrow{T_{k}}$. A _directed_ path (or _directed_ cycle) is an
orientation of a path (or cycle) such that the direction of each arc is same
to that of its predecessor. For convenience, we denote by $P_{k}$ (or
$\overrightarrow{P_{k}}$) the path (or directed path) and $C_{k}$ (or
$\overrightarrow{C_{k}}$) the cycle (or directed cycle) with $k$ vertices. For
a digraph $D$, the underlying multigraph ${\rm Umg}(D)$ of $D$ is a multigraph
obtained from $D$ by forgetting the direction on each arc of $D$. The
underlying graph ${\rm Ung}(D)$ of $D$ is obtained from ${\rm Umg}(D)$ by
replacing every pair of parallel edges with one. For example, for a digraph
$D$ with vertices $u$, $v$ and arcs $(u,v)$, $(v,u)$, ${\rm Umg}(D)$ has two
parallel edges between $u,v$ and ${\rm Ung}(D)$ has only one. Accordingly, for
a graph $G$, the double orientation $\overleftrightarrow{G}$ of $G$ is a
digraph obtained from $G$ by replacing every edge $\\{u,v\\}$ of $G$ with two
arcs $(u,v)$ and $(v,u)$. Note that ${\rm Ung}(\overleftrightarrow{G})=G$ and
$a(\overleftrightarrow{G})=2e(G)$.

As usual, in graphs we use $uv$ to denote the edge $\\{u,v\\}$ for short, and
in digraphs we use $uv$ to denote the arc $(u,v)$. For a digraph $D=(V,A)$
with $u,v\in V$, if $uv\in A$, we denote it by $u\rightarrow v$. If $uv\notin
A$, we denote it by $u\nrightarrow v$. Furthermore, if $uv\in A$ and $vu\notin
A$, we denote it by $u\mapsto v$. Analogously, for two subset $U,W\subseteq
V$, we write $U\rightarrow W$ if $u\rightarrow v$ for every $u\in U$ and $v\in
W$, and write $U\nrightarrow W$ if $u\nrightarrow v$ for every $u\in U$ and
$v\in W$. The notation $U\mapsto W$ means that $U\rightarrow W$ and
$W\nrightarrow U$. If $U$ (or $W$) consists of a single vertex $x$, then we
simply write $x\rightarrow W$, $x\nrightarrow W$ and $x\mapsto W$ (or
$U\rightarrow x$, $U\nrightarrow x$, and $U\mapsto x$).

Let $k\geq 1$ be an integer. A graph $G$ is called $k$-partite if $V(G)$
admits a partition into $k$ classes such that every edge has its ends in
different classes. A $k$-partite graph is called complete $k$-partite if its
any two vertices from different partition sets are adjacent. We denote by
$K_{n_{1},n_{2},\ldots,n_{k}}$ the complete $k$-partite graph with partition
sets of size $n_{1},n_{2},\ldots,n_{k}$. A partition of a vertex set is an
almost balanced partition if its partition sets differ in size by at most $1$.
Thus, a complete graph $K_{k}$ can be thought as a complete $k$-partite graph
such that each partition set has exactly one vertex. Denote by $K^{s}_{k}$ the
complete $k$-partite graph whose each partition set has exactly $s$ vertices.

For a directed path $\overrightarrow{P}$ and $u,v\in V(\overrightarrow{P})$,
we use $\overrightarrow{P}[u,v]$ to denote the directed sub-path from $u$ to
$v$. For a directed cycle $\overrightarrow{C}$ and $u,v\in
V(\overrightarrow{C})$, we use $\overrightarrow{C}[u,v]$ to denote the
directed path from $u$ to $v$ along $\overrightarrow{C}$.

We use $G_{1}\cup G_{2}$ to denote the _disjoint union_ of the two graphs
$G_{1},G_{2}$; and $G_{1}\vee G_{2}$ to denote the _join_ of $G_{1},G_{2}$,
that is, the graphs with vertex set $V(G_{1})\cup V(G_{2})$ and edge set
$E(G_{1})\cup E(G_{2})\cup\\{uv:u\in V(G_{1}),v\in V(G_{2})\\}$. The disjoint
union of $k$ copies of $G$ is denoted by $kG$, and the _complement_ of $G$,
denoted by $\overline{G}$, is the graphs on $V(G)$ such that for two vertices
$u,v\in V(G)$, $uv\in E(\overline{G})$ if and only if $uv\notin E(G)$.

Turán’s theorem [22] gave the unique $K_{k+1}$-free extremal graph of order
$n$, which we shall denote by $T_{n,k}$ and call it the _Turán graph._ The
Turán graph $T_{n,k}$ is a complete $k$-partite graph with an almost balanced
partition on $n$ vertices.

######  Theorem 1.1 (Turán [22]).

Let $n,k\in\mathbb{N}^{*}$, $n=qk+r,\ 0\leq r<k$. Then

${\rm ex}(n,K_{k+1})=e(T_{n,k})=\frac{k-1}{2k}n^{2}-\frac{r(k-r)}{2k},$

and ${\rm EX}(n,K_{k+1})=\\{T_{n,k}\\}$.

Further, for any given $K^{s}_{k}$, the famous Erdős-Stone theorem gave the
upper bound of Turán number ${\rm ex}(n,K^{s}_{k})$.

######  Theorem 1.2 (Erdős, Stone [11]).

For all $k,s\in\mathbb{N}^{*}$, and any $\varepsilon>0$, there exists an
integer $n_{0}$ such that for all $n\geq n_{0}$, we have

${\rm ex}(n,K^{s}_{k+1})<e(T_{n,k})+\varepsilon n^{2}.$

Let $n,k\in\mathbb{N}^{*}$ with $n=qk+r$ and $0\leq r<k$. In this paper, We
set $\varGamma_{n,k}:=qK_{k}\cup K_{r}$, that is, the the graph consists of
$q$ copies of $K_{k}$ and one copy of $K_{r}$. In addition, if $k\geq 3$ is
odd, $r=(k\pm 1)/2$ and $0\leq\ell\leq q$, we define the graph
$\varGamma_{n,k,\ell}:=(q-\ell)K_{k}\cup(K_{(k-1)/2}\vee\overline{K_{\ell
k+r-(k-1)/2}})$. Note that $\varGamma_{n,k,0}=\varGamma_{n,k}$.

######  Theorem 1.3 (Faudree, Schelp [14]).

Let $n,k\in\mathbb{N}^{*}$, $n=qk+r,\ 0\leq r<k$. Then

${\rm ex}(n,P_{k+1})=e(\varGamma_{n,k})=\frac{k-1}{2}n-\frac{r(k-r)}{2},$

and ${\rm EX}(n,P_{k+1})=\\{\varGamma_{n,k}\\}$ except for $k\geq 3$ is odd
and $r=(k\pm 1)/2$, in which case ${\rm
EX}(n,P_{k+1})=\\{\varGamma_{n,k,\ell}:0\leq\ell\leq q\\}$.

A path (or cycle) of a graph $G$ or a directed path (or directed cycle) of a
digraph $D$ is called Hamilton one if it contains every vertex of $G$ or $D$.
We will also use the following classic result in this paper.

######  Theorem 1.4 (Rédei [2]).

Every tournament contains a Hamilton directed path.

###  1.2 Our results

####  1.2.1 The Turán problem of directed paths

For integers $k,\ell$, we denote by $[k,\ell]$ the set of integers $i$ with
$k\leq i\leq\ell$. For $n,k\in\mathbb{N}^{*}$ with $n\geq k$, we define a
class of digraphs on $n$ vertices, denoted by $\overrightarrow{T_{n,k}}$,
which satisfies the following properties:

  1. (i)

$V(\overrightarrow{T_{n,k}})$ has an almost balanced partition
$\\{V_{1},V_{2},\ldots,V_{k}\\}$;

  2. (ii)

$V_{i}$ is an independent set of $\overrightarrow{T_{n,k}}$ for $i\in[1,k]$;

  3. (iii)

for any two parts $V_{i}$ and $V_{j}$ with $1\leq i<j\leq k$, $V_{i}\mapsto
V_{j}$ (see Figure 1).

Remark: Note that there may be more than one non-isomorphic
$\overrightarrow{T_{n,k}}$ for given $n,k$. However all the
$\overrightarrow{T_{n,k}}$ have the same arc number. We denote by
$\overrightarrow{\mathcal{T}_{n,k}}$ the set of all
$\overrightarrow{T_{n,k}}$. Observe that the underlying multigraph of
$\overrightarrow{T_{n,k}}$ is the Turán graph $T_{n,k}$. We sometimes call
$\overrightarrow{T_{n,k}}$ a _transitive orientation_ of $T_{n,k}$.

$V_{1}$$V_{2}$$V_{k-1}$$V_{k}$Figure 1. Digraph $\overrightarrow{T_{n,k}}$

Now we deal with the Turán Problem for directed paths
$\overrightarrow{P_{k+1}}$. For $k=1$, the $\overrightarrow{P_{2}}$-free
digraph is empty, and thus ${\rm ex}(n,\overrightarrow{P_{2}})=0$. For $k=2$,
clearly ${\rm ex}(1,\overrightarrow{P_{3}})=0$, ${\rm
ex}(2,\overrightarrow{P_{3}})=2$, and when $n\geq 3$, we have the following
result.

######  Theorem 1.5.

For all $n\geq 3$,

${\rm
ex}(n,\overrightarrow{P_{3}})=a(\overrightarrow{T_{n,2}})=\left\lfloor{\frac{n^{2}}{4}}\right\rfloor,$

and ${\rm EX}(n,\overrightarrow{P_{3}})=\overrightarrow{\mathcal{T}_{n,2}}$
for $n\geq 5$; and ${\rm
EX}(n,\overrightarrow{P_{3}})=\overrightarrow{\mathcal{T}_{n,2}}\cup\\{\overleftrightarrow{\varGamma_{n,2}}\\}$
for $n=3,4$.

However, for $k\geq 3$ and $n$ is small, it is difficult to determine the
precise Turán number ${\rm ex}(n,\overrightarrow{P_{k+1}})$. With more effort,
we prove the following result.

######  Theorem 1.6.

For every $k\in\mathbb{N}^{*}$, there exists $n_{0}$ such that if $n\geq
n_{0}$, $n=qk+r,\ 0\leq r<k$, then

${\rm
ex}(n,\overrightarrow{P_{k+1}})=a(\overrightarrow{T_{n,k}})=\frac{k-1}{2k}n^{2}-\frac{r(k-r)}{2k},$

and ${\rm EX}(n,\overrightarrow{P_{k+1}})=\overrightarrow{\mathcal{T}_{n,k}}$.

######  Corollary 1.1.

For all $k,n\in\mathbb{N}^{*}$,

${\rm ex}(n,\overrightarrow{P_{k+1}})\leq{\rm ex}(n,K_{k+1})+{\rm
ex}(n,P_{k+1}).$

####  1.2.2 The Turán problem of directed cycles

For integers $n,k\in\mathbb{N}^{*}$, $n=qk+r,\ 0\leq r<k$, we define a class
of digraphs on $n$ vertices, denoted by $\overrightarrow{F_{n,k}}$, which
satisfies the following properties (set $q^{\prime}=q$ if $r=0$ and
$q^{\prime}=q+1$ otherwise):

  1. (i)

$V(\overrightarrow{F_{n,k}})$ has a partition
$\\{V_{1},V_{2},\ldots,V_{q^{\prime}}\\}$ such that $|V_{i}|=k$ for all but at
most one $V_{i}$;

  2. (ii)

$\overrightarrow{F_{n,k}}[V_{i}]$ is a complete digraph for
$i\in[1,q^{\prime}]$;

  3. (iii)

for any two parts $V_{i}$ and $V_{j}$ with $1\leq i<j\leq q^{\prime}$,
$V_{i}\mapsto V_{j}$ (see Figure 2).

Note that there may be more than one non-isomorphic $\overrightarrow{F_{n,k}}$
for given $n,k$. However all $\overrightarrow{F_{n,k}}$ have the same arc
number. We denote by $\overrightarrow{\mathcal{F}_{n,k}}$ the set of all
$\overrightarrow{F_{n,k}}$.

$\overleftrightarrow{K_{k}}$$\overleftrightarrow{K_{k}}$$\overleftrightarrow{K_{r}}$$\overleftrightarrow{K_{k}}$$\underbrace{\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ }$$q$copies of $\overleftrightarrow{K_{k}}$ and one copy of
$\overleftrightarrow{K_{r}}$

Figure 2. Digraph $\overrightarrow{F_{n,k}}$.

Now we deal with the Turán problem for directed cycles
$\overrightarrow{C_{k}}$. First, for $k\in\\{2,3\\}$, $\overrightarrow{C_{2}}$
can be regarded as a complete digraph $\overleftrightarrow{K_{2}}$, and
$\overrightarrow{C_{3}}$ can be regarded as a tournament
$\overrightarrow{T_{3}}$. For complete digraph $\overleftrightarrow{K_{k}}$
and tournament $\overrightarrow{T_{k}}$, let us recall the results of Brown
and Harary [5].

######  Theorem 1.7 (Brown, Harary [5]).

Let $k,n\in\mathbb{N}^{*}$, then

${\rm ex}(n,\overleftrightarrow{K_{k+1}})=\binom{n}{2}+{\rm
ex}(n,K_{k+1})\mbox{ and \ }{\rm ex}(n,\overrightarrow{T_{k+1}})=2{\rm
ex}(n,K_{k+1}).$

Moreover, Brown and Harary characterized all the extremal digraphs for
$\overleftrightarrow{K_{k}}$ and $\overrightarrow{T_{k}}$. Therefore, the
Turán number and the extremal digraphs for $\overrightarrow{C_{2}}$ and
$\overrightarrow{C_{3}}$ can be known directly by the results of Brown and
Harary. For any directed cycles $\overrightarrow{C_{k+1}}$, $k\geq 3$, we have
the following result.

######  Theorem 1.8.

Let $k,n\in\mathbb{N}^{*}$, $n=qk+r$, $0\leq r<k$. Then

${\rm
ex}(n,\overrightarrow{C_{k+1}})=a(\overrightarrow{F_{n,k}})=\frac{1}{2}n^{2}+\frac{k-2}{2}n-\frac{r(k-r)}{2}.$

Furthermore, ${\rm
EX}(n,\overrightarrow{C_{k+1}})=\overrightarrow{\mathcal{F}_{n,k}}$ for $k\geq
3$.

It is worth mentioning that for $\overrightarrow{C_{2}}$ and
$\overrightarrow{C_{3}}$, there are extremal graphs other than that in
$\overrightarrow{\mathcal{F}_{n,1}}$ and $\overrightarrow{\mathcal{F}_{n,2}}$
(see [5]). In addition, by Theorem 1.8, we can easily obtain the following
corollary about Hamilton directed cycle.

######  Corollary 1.2.

Every digraph with $n\geq 2$ vertices and at least $n^{2}-2n+2$ arcs contains
a Hamilton directed cycle.

####  1.2.3 The Turán problem of orientations of $C_{4}$

Finally, we will complete the Turán problem of all orientations of $C_{4}$.
There are four orientations for $C_{4}$, we denote by
$\overrightarrow{C_{4}}$, $\overrightarrow{K_{2,2}}$,
$\overrightarrow{P_{2,2}}$ and $\overrightarrow{P_{1,3}}$ (see Figure 3).

$\overrightarrow{C_{4}}$$\overrightarrow{K_{2,2}}$$\overrightarrow{P_{2,2}}$$\overrightarrow{P_{1,3}}$

Figure 3. The orientations of $C_{4}$.

As mentioned earlier, the Turán problem of $\overrightarrow{P_{2,2}}$ has been
solved by Huang and Lyu in [19] (for $n\geq 13$), and the Turán number of
$\overrightarrow{C_{4}}$ can be obtained directly from Theorem 1.8. Now we
deal with the Turán problem of $\overrightarrow{P_{1,3}}$ and
$\overrightarrow{K_{2,2}}$.

From the following Theorems 1.9 and 1.10, one can see that ${\rm
ex}(n,\overrightarrow{P_{1,3}})=\max\\{2{\rm ex}(n,C_{4}),{\rm
ex}(n,K_{4})\\}$.

######  Theorem 1.9.

For $n\in[1,8]$, ${\rm ex}(n,\overrightarrow{P_{1,3}})=2{\rm ex}(n,C_{4})$,
and ${\rm EX}(n,\overrightarrow{P_{1,3}})=\\{\overleftrightarrow{H}:H\in{\rm
EX}(n,C_{4})\\}$.

Computer searches by Clapham et al. [10] and Yang and Rowlinson [31]
determined ${\rm EX}(n,C_{4})$ for all $n\leq 31$. We list the $C_{4}$-free
extremal graphs for all $n$ up to $8$ (see Figure 4).

${\rm{EX}}(8,C_{4})$, ${\rm{ex}}(8,C_{4})=11$${\rm{EX}}(7,C_{4})$,
${\rm{ex}}(7,C_{4})=9$${\rm{EX}}(6,C_{4})$,
${\rm{ex}}(6,C_{4})=7$${\rm{EX}}(1,C_{4})$,${\rm{ex}}(1,C_{4})=0$${\rm{EX}}(2,C_{4})$,${\rm{ex}}(2,C_{4})=1$${\rm{EX}}(3,C_{4})$,${\rm{ex}}(3,C_{4})=3$${\rm{EX}}(4,C_{4})$,${\rm{ex}}(4,C_{4})=4$${\rm{EX}}(5,C_{4})$,${\rm{ex}}(5,C_{4})=6$

Figure 4. Extremal graphs for $C_{4}$ with $n\in[1,8]$.

For $n\geq 9$, we first define a class of $\overrightarrow{P_{1,3}}$-free
digraphs on $n$ vertices, namely symmetric multipartite digraph, denoted by
$\overrightarrow{S_{n}}$, which satisfies the following properties (see Figure
5):

  1. (i)

$V(\overrightarrow{S_{n}})$ has an almost balanced partition $\\{X,Y,Z\\}$;

  2. (ii)

$X$, $Y$ and $Z$ are independent sets of $\overrightarrow{S_{n}}$;

  3. (iii)

$X$, $Y$, $Z$, respectively, has a partition $\\{X_{1},X_{2}\\}$,
$\\{Y_{1},Y_{2}\\}$, $\\{Z_{1},Z_{2}\\}$ (possibly $X_{i},Y_{j}$ or
$Z_{k}=\emptyset$);

  4. (iv)

$X_{1}\mapsto Y_{1}\cup Z_{2}$, $Y_{1}\mapsto Z_{1}\cup X_{2}$, $Z_{1}\mapsto
X_{1}\cup Y_{2}$, $X_{2}\mapsto Y_{2}\cup Z_{1}$, $Y_{2}\mapsto Z_{2}\cup
X_{1}$, $Z_{2}\mapsto X_{2}\cup Y_{1}$.

Remark: There is no relationship between the size of $X_{1}$ and $X_{2}$, and
the same for $Y_{1}$ and $Y_{2}$, $Z_{1}$ and $Z_{2}$. Note that there may be
more than one non-isomorphic $\overrightarrow{S_{n}}$ for given $n$. However,
all $\overrightarrow{S_{n}}$ have the same arc number, and the underlying
multigraph of $\overrightarrow{S_{n}}$ is only the Turán graph $T_{n,3}$. We
denote by $\overrightarrow{\mathcal{S}_{n}}$ the set of all
$\overrightarrow{S_{n}}$.

$X_{1}$$Z_{2}$$Y_{1}$$X_{2}$$Z_{1}$$Y_{2}$

Figure 5. Digraph $\overrightarrow{S_{n}}$.

######  Theorem 1.10.

For all $n\geq 9$,

${\rm
ex}(n,\overrightarrow{P_{1,3}})=a(\overrightarrow{S_{n}})=\left\lfloor\frac{n^{2}}{3}\right\rfloor.$

Furthermore,
${\rm{EX}}(n,\overrightarrow{P_{1,3}})=\overrightarrow{\mathcal{S}_{n}}$.

For $\overrightarrow{K_{2,2}}$, we are surprised to find that to calculate the
Turán number of $\overrightarrow{K_{2,2}}$ is as difficult as to $C_{4}$ in
bipartite graphs. Given a bipartite graph $H$, let ${\rm ex}(n,n;H)$ denote
the maximum number of edges in a $H$-free bipartite graph with partition sets
of equal size $n$; and let ${\rm EX}(n,n;H)$ denote the set of all the
$H$-free bipartite graph with ${\rm ex}(n,n;H)$ edges and with partition sets
of equal size $n$.

Given a digraph $D$ with $V(D)=\\{v_{i}:i\in[1,n]\\}$, we define the
_bipartite representation_ of $D$ as a bipartite graph $B$ with partition sets
$X=\\{x_{i}:i\in[1,n]\\}$ and $Y=\\{y_{i}:i\in[1,n]\\}$ such that
$x_{i}y_{j}\in E(B)$ if and only if $v_{i}v_{j}\in A(D)$. We denote by ${\rm
Brp}(D)$ the bipartite representation of $D$.

######  Theorem 1.11.

For $n\in\mathbb{N}^{*}$ with $n\geq 3$,

${\rm ex}(n,\overrightarrow{K_{2,2}})={\rm ex}(n,n;C_{4}).$

Furthermore, ${\rm{EX}}(n,\overrightarrow{K_{2,2}})=\\{D:{\rm
Brp}(D)\in{\rm{EX}}(n,n;C_{4})\\}$.

The paper is organized as follows. The results of directed paths are proved in
Section 2. The results of directed cycles are proved in Section 3. In Section
4, we prove the results of $\overrightarrow{P_{1,3}}$ and
$\overrightarrow{K_{2,2}}$. Finally, we close the paper with some remarks and
conjectures in Section 5.

##  2 The proofs for directed paths

In this section, we prove Theorem 1.5 and Theorem 1.6. Corollary 1.1 can be
directly obtained from the proof of Theorem 1.6 (see bellow). From now on, let
$n,k\in\mathbb{N}^{*}$ with $k\geq 2$, $n=qk+r,\ 0\leq r<k$.

###### Proof of Theorem 1.5.

Let $D\in{\rm EX}(n,\overrightarrow{P_{3}})$, and let $\mathcal{C}$ denote the
set of all $\overrightarrow{C_{2}}$ in $D$, $t=|\mathcal{C}|$. Since $D$ is
$\overrightarrow{P_{3}}$-free, every $\overrightarrow{C_{2}}$ is a component
of $D$. Let $D^{\prime}$ be the digraph obtained from $D$ by removing all the
$\overrightarrow{C_{2}}$-components. Then ${\rm Umg}(D^{\prime})$ is a simple
graph. Moreover, ${\rm Umg}(D^{\prime})$ is also $K_{3}$-free by Theorem 1.4.
Hence $a(D^{\prime})\leq{\rm
ex}(|V(D^{\prime})|,K_{3})=\lfloor{\frac{(n-2t)^{2}}{4}}\rfloor$ by Theorem
1.1. Therefore, for $n\geq 3$, we obtain that

$a(D)\leq
2t+\left\lfloor{\frac{(n-2t)^{2}}{4}}\right\rfloor\leq\left\lfloor{\frac{n^{2}}{4}}\right\rfloor.$

Note that the first equality holds only if $a(D^{\prime})={\rm
ex}(|V(D^{\prime})|,K_{3})$, and the second equality holds only if $t=0$ for
$n\geq 3$, or $t=\lfloor\frac{n}{2}\rfloor$ for $n=3,4$. Furthermore, when
$t=0$, then ${\rm Umg}(D)$ is the $K_{3}$-free extremal graph $T_{n,2}$. It is
easy to see that an orientation of $T_{n,2}$ is $\overrightarrow{P_{3}}$-free
if and only if it is a transitive orientation. If $n\in\\{3,4\\}$ and
$t=\lfloor\frac{n}{2}\rfloor$, then clearly
$D=\overleftrightarrow{\varGamma_{n,2}}$. Thus we have ${\rm
EX}(n,\overrightarrow{P_{3}})=\overrightarrow{\mathcal{T}_{n,2}}\cup\\{\overleftrightarrow{\varGamma_{n,2}}\\}$
for $n\in\\{3,4\\}$, and ${\rm
EX}(n,\overrightarrow{P_{3}})=\overrightarrow{\mathcal{T}_{n,2}}$ for $n\geq
5$. ∎

###### Proof of Theorem 1.6.

From now on, let $D\in{\rm EX}(n,\overrightarrow{P_{k+1}})$. Since
$\overrightarrow{T_{n,k}}$ is a $\overrightarrow{P_{k+1}}$-free digraph,
$a(D)\geq a(\overrightarrow{T_{n,k}})={\rm ex}(n,K_{k+1})$. Our main aim is to
prove $D\in\overrightarrow{\mathcal{T}_{n,k}}$ for large $n$. For this, we
will need two key claims.

######  Claim 2.1.

The digraph $D$ contains an induced subdigraph $\overrightarrow{T_{k^{2},k}}$.

###### Proof.

Let $\mathcal{C}$ still denote the set of all $\overrightarrow{C_{2}}$ in $D$
and $t=|\mathcal{C}|$. By Theorem 1.3, we have $t\leq{\rm ex}(n,P_{k+1})$.
Consider the graph $G:={\rm Ung}(D)$. On the one hand, since Theorem 1.4
implies that $G$ is $K_{k+1}$-free, we have $e(G)\leq{\rm ex}(n,K_{k+1})$. (We
remark that this implies that $a(D)\leq{\rm ex}(n,P_{k+1})+{\rm
ex}(n,K_{k+1})$, and thus Corollary 1.1 holds.) On the other hand, since
$a(D)\geq e(T_{n,k})$, by Theorem 1.3, we have

$e(G)=a(D)-t\geq e(T_{n,k})-{\rm ex}(n,P_{k+1})\geq
e(T_{n,k-1})+\frac{1}{2k^{2}}n^{2},$

for all $n\geq k^{4}$. By Theorem 1.2, there is an integer $n_{0}$ (which
depends only on $k$) such that for all $n\geq n_{0}$, $G$ contains a
$K_{k}^{k}=T_{k^{2},k}$ as a subgraph. Recall that $G$ is $K_{k+1}$-free.
Therefore, $G$ contains an induced subgraph $H$ isomorphic to $T_{k^{2},k}$.

Now consider the orientation of $H$ in $D$. Let
$\\{U_{1},U_{2},\ldots,U_{k}\\}$ be the partition of $V(H)$,
$S=\\{u_{1},u_{2},\ldots,u_{k}\\}$ be a subset of $V(H)$ with $u_{i}\in
U_{i}$, and $D[S]$ be the induced subgraph of $D$ on $S$. By Theorem 1.4,
$D[S]$ contains a $\overrightarrow{P_{k}}$. Without loss of generality, we
assume that $u_{i}\rightarrow u_{i+1}$ for $i\in[1,k-1]$.

Given $v_{j}\in U_{j}\setminus\\{u_{j}\\}$, we claim that $v_{j}\nrightarrow
u_{i}$ in $D$ for $i\in[1,j-1]$. Suppose not, then there is an arc
$v_{j}\rightarrow u_{i}$ with $i$ as small as possible. Clearly, $i\neq 1$,
otherwise $\overrightarrow{P}:=v_{j}u_{1}\ldots u_{k}$ is a
$\overrightarrow{P_{k+1}}$ in $D$, a contradiction. Now we assume that
$i\in[2,j-1]$. Note that we must have $u_{i-1}\rightarrow v_{j}$ in $D$ from
the minimality of $i$. In this case, $\overrightarrow{P}:=u_{1}\ldots
u_{i-1}v_{j}u_{i}\ldots u_{k}$ is also a $\overrightarrow{P_{k+1}}$, a
contradiction. Thus, we have $u_{i}\mapsto v_{j}$ in $D$ for all $v_{j}\in
U_{j}\setminus\\{u_{j}\\}$ and $1\leq i<j\leq k$. By a similar analysis, for
$v_{i}\in U_{i}\setminus\\{u_{i}\\}$, we can show that $v_{i}\mapsto u_{j}$ in
$D$ for $1\leq i<j\leq k$.

Next we show that for every $v_{i}\in U_{i}$ and $v_{j}\in U_{j}$ with $1\leq
i<j\leq k$, $v_{j}\nrightarrow v_{i}$ holds. If $v_{i}=u_{i}$ and $v_{j}\neq
u_{j}$, or $v_{i}\neq u_{i}$ and $v_{j}=u_{j}$, then we are done by the
analysis above. Suppose now that $v_{i}\neq u_{i}$ and $v_{j}\neq u_{j}$. Then
we have $u_{i}\rightarrow v_{j}$ and $v_{i}\rightarrow u_{i+1}$. If
$v_{j}\rightarrow v_{i}$, then $\overrightarrow{P}:=u_{1}\ldots
u_{i}v_{j}v_{i}u_{i+1}\ldots u_{k}$ is a $\overrightarrow{P_{k+2}}$ in $D$, a
contradiction. Finally, we consider the case $v_{i}=u_{i}$ and $v_{j}=u_{j}$.
Let $v^{\prime}_{i}$ be a vertex in $U_{i}\setminus\\{u_{i}\\}$. We have
$u_{i-1}\rightarrow v^{\prime}_{i}$ (if $i\geq 2$) and
$v^{\prime}_{i}\rightarrow u_{i+1}$. It follows that
$\overrightarrow{P}:=u_{1}\ldots u_{i-1}v^{\prime}_{i}u_{i+1}\ldots u_{k}$ is
also a $\overrightarrow{P_{k}}$ in $D$, and $v_{j}\nrightarrow v_{i}$ as well.
Thus we have $U_{i}\mapsto U_{j}$ in $D$ for $1\leq i<j\leq k$. This implies
that the subdigraph of $D$ induced by $V(H)$ is a
$\overrightarrow{T_{k^{2},k}}$. ∎

According to Claim 2.1, let $D_{1}$ be an induced
$\overrightarrow{T_{k^{2},k}}$ of $D$. For simplicity, let
$\\{U_{1},U_{2},\ldots,U_{k}\\}$ be the partition of $V(D_{1})$ with
$U_{i}\mapsto U_{j}$ for $1\leq i<j\leq k$. Thus $|U_{i}|=k$ for all
$i\in[1,k]$. Note that $U_{k}\nrightarrow v$ for every $v\in V(D)$ since $D$
is $\overrightarrow{P_{k+1}}$-free. Thus for every $v\in V(D)$, there is a
smallest $i$ such that $U_{i}\nrightarrow v$. We define a partition
$\\{V_{1},V_{2},\dots,V_{k}\\}$ of $V(D)$ as follow:

$V_{j}:=\left\\{v\in V(D):j=\min\left\\{i\in[1,k]:U_{i}\nrightarrow
v\right\\}\right\\}.$

Clearly, $V(D)=\bigcup_{i=1}^{k}V_{i}$, $V_{i}\cap V_{j}=\emptyset$ for $1\leq
i<j\leq k$, and $U_{i}\subseteq V_{i}$ for all $i\in[1,k]$. For every $v\in
V(D)$, by the arcs-maximality of $D$ (i.e., $D\in{\rm
EX}(n,\overrightarrow{P_{k+1}})$), we will obtain the following result.

######  Claim 2.2.

For $s\in[1,k]$, if $v\in V_{s}$ then $\bigcup_{i=s}^{k}V_{i}\nrightarrow v$
and $v\rightarrow\bigcup_{i=s+1}^{k}V_{i}$.

###### Proof.

Suppose the claim is not true for some $s$. We choose such an $s$ that is as
small as possible, and let $v\in V_{s}$ not satisfying the assertion. We first
show that there is a directed path of order $k-s+1$ starting from $v$. Let
$u\in U_{s}\setminus\\{v\\}$ and $D^{\prime}$ be the digraph obtained from $D$
by adding the arc $uv$. Since $D$ is extremal for $\overrightarrow{P_{k+1}}$,
$D^{\prime}$ contains a directed path $\overrightarrow{P}$ of order $k+1$
which passes through the added arc $uv$. Let $x,y$ be the origin and terminus
of $\overrightarrow{P}$. If $D$ has no path of order $k-s+1$ starting from
$v$, then $|V(\overrightarrow{P}[v,y])|\leq k-s$ and
$|V(\overrightarrow{P}[x,u])|\geq s+1$. Thus we can take $u_{i}\in
U_{i}\setminus V(\overrightarrow{P})$ with $i\in[s+1,k]$, then
$\overrightarrow{P}[x,u]uu_{s+1}\ldots u_{k}$ is a $\overrightarrow{P_{k+1}}$
in $D$, a contradiction. For simplicity, let $\overrightarrow{Q}$ be a
directed path of order $k-s+1$ starting from $v$.

Let $W=\\{w\in\bigcup_{i=s}^{k}V_{i}:w\rightarrow v\\}$. We will show that
$W=\emptyset$. First consider $s=1$. For $v\in V_{1}$, if $|W|\geq k$, then
there is a vertex $w\in W\setminus V(\overrightarrow{Q})$, which implies
$wv\overrightarrow{Q}$ is a $\overrightarrow{P_{k+1}}$, a contradiction. Now
assume that $1\leq|W|\leq k-1$. Let $w\in W$ be arbitrary. If $v\rightarrow
u_{2}$ for some $u_{2}\in U_{2}\backslash\\{w\\}$, then we can take $u_{i}\in
U_{i}$ with $i\in[3,k]$, and $wvu_{2}\ldots u_{k}$ is a
$\overrightarrow{P_{k+1}}$ in $D$, a contradiction. Thus we have
$v\nrightarrow U_{2}\backslash\\{w\\}$. Specially, if $|W|\geq 2$, then
$v\nrightarrow U_{2}$. Let $D^{\prime}$ be the digraph on $V(D)$ with arc set

$A(D^{\prime})=(A(D)\setminus\\{wv:w\in W\\})\cup\\{vu:u\in U_{2}\\},$

which yields another $\overrightarrow{P_{k+1}}$-free digraph with more arcs
than $D$, contradicting the choice of $D$.

Next, let $s\in[2,k-1]$. By the choice of $v$, we have that
$D[\bigcup_{i=1}^{s-1}V_{i}]$ is $\overrightarrow{P_{s}}$-free and
$\bigcup_{i=1}^{s-1}V_{i}\mapsto\bigcup_{i=s}^{k}V_{i}$. If $|W|\geq k-s+1$,
then there is a vertex $w\in W\setminus V(\overrightarrow{Q})$. Thus we can
take $u_{i}\in U_{i}$ with $i\in[1,s-1]$, then $u_{1}\ldots
u_{s-1}wv\overrightarrow{Q}$ is a $\overrightarrow{P_{k+1}}$ in $D$, a
contradiction. Now assume that $1\leq|W|\leq k-s$. Let $w\in W$ be arbitrary.
If $v\rightarrow u_{s+1}$ for some $u_{s+1}\in U_{s+1}\backslash\\{w\\}$, then
we can take $u_{i}\in U_{i}$ with $i\in[1,s-1]\cup[s+2,k]$, and $u_{1}\ldots
u_{s-1}wvu_{s+1}\ldots u_{k}$ is a $\overrightarrow{P_{k+1}}$ in $D$, a
contradiction. Thus we have $v\nrightarrow U_{s+1}\backslash\\{w\\}$.
Specially, if $|W|\geq 2$, then $v\nrightarrow U_{s+1}$. Let $D^{\prime}$ be
the digraph on $V(D)$ with arc set

$A(D^{\prime})=(A(D)\setminus\\{wv:w\in W\\})\cup\\{vu:u\in U_{s+1}\\}.$

Clearly $|A(D^{\prime})|>|A(D)|$, implying that $D^{\prime}$ contains a
directed path $\overrightarrow{P}=\overrightarrow{P_{k+1}}$ which passes
through an arc $vu$ with $u\in U_{s+1}$. Let $x,y$ be the origin and terminus
of $\overrightarrow{P}$. Clearly
$V(\overrightarrow{P}[x,v])\setminus\\{v\\}\subseteq\bigcup_{i=1}^{s-1}V_{i}$
and thus $|V(\overrightarrow{P}[x,v])|\leq s$. It follows that
$|V(\overrightarrow{P}[u,y])|\geq k-s+1$. Thus we can take $u_{i}\in U_{i}$
with $i\in[1,s]$, then $u_{1}\ldots u_{s}u\overrightarrow{P}[u,y]$ is a
$\overrightarrow{P_{k+1}}$ of $D$, a contradiction.

Finally let $s=k$. Thus $W\subseteq V_{k}$. If $W\neq\emptyset$, then we can
take $w\in W$, $u_{i}\in U_{i}$ for $i\in[1,k-1]$, and $u_{1}\ldots u_{k-1}wv$
is a $\overrightarrow{P_{k+1}}$ of $D$, a contradiction. In any case, we
proved that $W=\emptyset$, i.e., $\bigcup_{i=s}^{k}V_{i}\nrightarrow v$.

Suppose now that there is a vertex $u\in\bigcup_{i=s+1}^{k}V_{i}$ such that
$v\nrightarrow u$ in $D$. Let $D^{\prime}$ be the digraph obtained from $D$ by
adding the arc $vu$. Then $D^{\prime}$ contains a path
$\overrightarrow{P}=\overrightarrow{P_{k+1}}$ which passes through the arc
$vu$. Let $x,y$ be the origin and terminus of $\overrightarrow{P}$. Recall
that $\bigcup_{i=s}^{k}V_{i}\nrightarrow v$ and $D[\bigcup_{i=1}^{s-1}V_{i}]$
is $\overrightarrow{P_{s}}$-free. We have that
$|V(\overrightarrow{P}[x,v])|\leq s$ and $|V(\overrightarrow{P}[u,y])|\geq
k-s+1$ (we remark that if $s=1$, then $x=v$, and
$|V(\overrightarrow{P}[u,y])|\geq k$). Note that $U_{s}\nrightarrow u$ does
not hold, implying that there is a vertex $u_{s}\in U_{s}$ with
$u_{s}\rightarrow u$. Thus we can take $u_{i}\in U_{i}$, $i\in[1,s-1]$, and
$u_{1}\ldots u_{s}u\overrightarrow{P}[u,y]$ contains a
$\overrightarrow{P_{k+1}}$ of $D$, a contradiction. Thus we have $v\rightarrow
u$ for all $u\in\bigcup_{i=s+1}^{k}V_{i}$. ∎

According to Claim 2.2, it is easy to see that the partition
$\\{V_{1},V_{2},\dots,V_{k}\\}$ of $V(D)$ satisfies the Properties (ii) and
(iii) in the definition of $\overrightarrow{T_{n,k}}$. When $D$ also satisfies
the Property (i) in the definition of $\overrightarrow{T_{n,k}}$, $D$ has the
maximum number of arcs. Therefore, $D\in\overrightarrow{\mathcal{T}_{n,k}}$. ∎

##  3 The proof for directed cycles

In this section, we aim to prove Theorem 1.8. For simplicity, let
$f(n,k)=a(\overrightarrow{F_{n,k}})$ for all $n,k\in\mathbb{N}^{*}$.

###### Proof of Theorem 1.8.

We use double induction on $n$ and $k$. For $k=1,2$, we are done by Theorem
1.7. Now we assume that $k\geq 3$. When $n\leq k$, clearly
$\overleftrightarrow{K_{n}}=\overrightarrow{F_{n,k}}$ is the unique extremal
digraph for $\overrightarrow{C_{k+1}}$ and ${\rm
ex}(n,\overrightarrow{C_{k+1}})=f(n,k)$. For the induction step, assume that
$n\geq k+1$ and ${\rm
ex}(n^{\prime},\overrightarrow{C_{k+1}})=f(n^{\prime},k)$ holds for all
$n^{\prime}<n$.

Let $D\in{\rm EX}(n,\overrightarrow{C_{k+1}})$, then $a(D)\geq f(n,k)$ since
$\overrightarrow{F_{n,k}}$ is $\overrightarrow{C_{k+1}}$-free. Due to
$f(n,k)>f(n,k-1)$ for all $n\geq k$, $D$ contains a directed cycle
$\overrightarrow{C}=\overrightarrow{C_{k}}$. Let
$V(\overrightarrow{C})=\\{u_{1},u_{2},\ldots,u_{k}\\}$ with $u_{i}u_{i+1}\in
A(\overrightarrow{C})$ (the subscripts are taken modulo $k$) and
$V^{\prime}=V(D)\setminus V(\overrightarrow{C})$. Clearly
$a(D[V(\overrightarrow{C})])\leq k(k-1)$. By the induction hypothesis,
$D[V^{\prime}]$ has at most $f(n-k,k)$ arcs.

For $v\in V^{\prime}$, we claim that there are at most $k$ arcs between
$V(\overrightarrow{C})$ and $v$. For otherwise there will be two vertices
$u_{i},u_{i+1}$ with $u_{i}\rightarrow v$ and $v\rightarrow u_{i+1}$, and thus
$\overrightarrow{C^{\prime}}=u_{i}vu_{i+1}\overrightarrow{C}[u_{i+1},u_{i}]$
is a $\overrightarrow{C_{k+1}}$ in $D$. Hence, we have

$a(D)\leq k(k-1)+k(n-k)+f(n-k,k)=f(n,k).$

The equality on the right follows by the definition of $f(n,k)$. Since
$a(D)\geq f(n,k)$, we have equality in above formula. Thus,
$D[V(\overrightarrow{C})]$ must be a $\overleftrightarrow{K_{k}}$, the number
of arcs between $V(\overrightarrow{C})$ and every vertex in $V^{\prime}$ is
exactly $k$, and $D[V^{\prime}]$ is an extremal digraph for
$\overrightarrow{C_{k+1}}$ and $n-k$.

For every $v\in V^{\prime}$, since $D[V(\overrightarrow{C})]$ is a
$\overleftrightarrow{K_{k}}$, these $k$ arcs between $v$ and
$V(\overrightarrow{C})$ must have the same direction. For two distinct
vertices $u,v\in V^{\prime}$, if $uv$ and $vu$ are all in $A(D)$, then the
direction of the arcs between $V(\overrightarrow{C})$ and $u$ must be the same
as that between $V(\overrightarrow{C})$ and $v$. Therefore, by recursive
induction, we can obtain that the structure of $D$ can only be a
$\overrightarrow{F_{n,k}}$. ∎

##  4 The proofs for orientations of $C_{4}$

In this section, we will prove Theorem 1.9, Theorem 1.10 and Theorem 1.11,
respectively. To prepare for this we will need some notation. We follow [2]
and [11]. Let $G=(V,E)$ be a graph, for $v\in V$, the neighborhood of $v$ is
denoted by $N_{G}(v):=\\{u\in V:uv\in E\\}$, and the degree of $v$ is
$d_{G}(v)=|N_{G}(v)|$. Analogously, given a digraph $D=(V,A)$ and $v\in V$, we
use the following notation:

$N^{+}_{D}(v):=\\{u\in V:(v,u)\in A\\},\ N^{-}_{D}(v):=\\{w\in V:(w,v)\in
A\\}.$

The set $N^{+}_{D}(v)$, $N^{-}_{D}(v)$ and $N_{D}(v)=N^{+}_{D}(v)\cup
N^{-}_{D}(v)$ are called the out-neighborhood, in-neighborhood and
neighborhood of $v$. The out-degree, the in-degree, and the degree of $v$ are
denoted by $d^{+}_{D}(v):=|N^{+}_{D}(v)|$, $d^{-}_{D}(v):=|N^{-}_{D}(v)|$, and
$d_{D}(v):=d^{+}_{D}(v)+d^{-}_{D}(v)$. For $i,j,k\in\mathbb{N}^{*}$, by
$\varTheta_{i,j,k}$ we mean the graph (or multigraph) consisting of three
internally-disjoint paths of lengths $i,j,k$, respectively, with the same
origin and the same terminus.

Next, we state several lemmas that are useful for the proofs of Theorem 1.9
and Theorem 1.10.

######  Lemma 4.1.

Every orientation of $K_{4}$ and $\varTheta_{1,1,3}$ contains a
$\overrightarrow{P_{1,3}}$.

In Figure 6 we list all the (non-isomorphic) orientations of $K_{4}$ and
$\varTheta_{1,1,3}$ together with the $\overrightarrow{P_{1,3}}$-subdigraphs,
which directly proves Lemma 4.1.

######  Lemma 4.2.

For $n\leq 8$, every non-empty $K_{4}$-free graph $G$ on $n$ vertices contains
a $C_{4}$-free subgraph $H$ with $e(H)>e(G)/2$.

The proof of Lemma 4.2 needs some technic analysis, which we postpone to the
last part of the section.

Figure 6. Orientations of $K_{4}$ and $\varTheta_{1,1,3}$.

###### Proof of Theorem 1.9..

Let $D$ be a $\overrightarrow{P_{1,3}}$-free extremal digraph on $n\leq 8$
vertices. Then $a(D)\geq 2{\rm ex}(n,C_{4})$. Let $G={\rm Ung}(D)$, $G_{1}$ be
the graph obtained from ${\rm Umg}(D)$ by removing all edges of $C_{2}$, and
$G_{2}$ be the subgraph of $G$ with edge set $E(G)\setminus E(G_{1})$. By
Lemma 4.1, $G_{1}$ is $K_{4}$-free and every edge in $E(G_{2})$ is not
contained in a $C_{4}$ of $G$. Assume first that $E(G_{1})\neq\emptyset$. By
Lemma 4.2, $G_{1}$ has a $C_{4}$-free subgraph $H_{1}$ with
$e(H_{1})>e(G_{1})/2$. Now the union of $H_{1}$ and $G_{2}$ is a $C_{4}$-free
graph $H$ with $e(H)>a(D)/2$. It follows that $\overleftrightarrow{H}$ is a
$\overrightarrow{P_{1,3}}$-free digraph with arc number greater than $D$, a
contradiction. Therefore, we conclude that $E(G_{1})=\emptyset$ and $G=G_{2}$
is $C_{4}$-free. Since $D$ is a extremal digraph, $e(G)=a(D)/2={\rm
ex}(n,C_{4})$, which implies that $G\in{\rm EX}(n,C_{4})$, and we are done. ∎

###### Proof of Theorem 1.10..

We prove Theorem 1.10 using induction on $n$. When $n=9$, we first prove the
following result:

${\rm ex}(9,\overrightarrow{P_{1,3}})=27\ \text{and \ }{\rm
EX}(9,\overrightarrow{P_{1,3}})=\overrightarrow{\mathcal{S}_{9}}.$

Let $D\in{\rm EX}(9,\overrightarrow{P_{1,3}})$, then $a(D)\geq
a(\overrightarrow{S_{9}})=27$ since $\overrightarrow{S_{9}}$ is
$\overrightarrow{P_{1,3}}$-free. By Theorem 1.9, we have ${\rm
ex}(8,\overrightarrow{P_{1,3}})=22$, which implies that $d_{D}(v)\geq 5$ for
all $v\in V(D)$. Suppose now that there is $v_{0}\in V(D)$ such that
$D_{1}:=D-v_{0}$ is an extremal digraph in ${\rm
EX}(8,\overrightarrow{P_{1,3}})$, i.e., $D_{1}$ is the double orientation of a
graph in ${\rm EX}(8,C_{4})$. Let $G={\rm Ung}(D)$, then $G$ has to be
$C_{4}$-free, for otherwise ${\rm Umg}(D)$ contains a $\varTheta_{1,1,3}$ and
$D$ contains a $\overrightarrow{P_{1,3}}$ by Lemma 4.1. For convenience, we
define ${\rm Inj}(G)$ as the  _injective graph_ of $G$, which is the graph on
$V(G)$ such that $uv\in E({\rm Inj}(G))$ if and only if $N_{G}(u)\cap
N_{G}(v)\neq\emptyset$. One can check that every graph in ${\rm EX}(8,C_{4})$
(see Figure 4) satisfies that the independent number of its injective graph is
$2$. Recall that $d_{D}(v_{0})\geq 5$, implying that $d_{G}(v_{0})\geq 3$
(possibly $v$ is incident with some $\overrightarrow{C_{2}}$ in $D$). This
implies that $N_{G}(v_{0})$ contains two vertices $v_{1},v_{2}$ such that
$v_{1},v_{2}$ have a common neighbor in ${\rm Ung}(D_{1})$. Then $G$ contains
a $C_{4}$, a contradiction. Thus, we conclude that $a(D-v)<22$ for $v\in
V(D)$. An easy averaging argument shows that there exists $v^{\prime}\in V(D)$
such that $d_{D}(v^{\prime})\leq 6$. If $a(D)=28$, then $a(D-v^{\prime})\geq
22$, a contradiction. This implies that $D$ has exactly $27$ arcs and
$d_{D}(v)=6$ for all $v\in V(D)$.

In the following we will show that $D$ has no $\overrightarrow{C_{2}}$. Let
$\mathcal{C}$ denote the set of all $\overrightarrow{C_{2}}$ in $D$. Suppose
first that $|\mathcal{C}|\geq 5$. Let $D_{1}$ be the subgraph of $D$ by
removing arcs of all $\overrightarrow{C_{2}}$. Since $a(D)$ is odd, $D_{1}$ is
not empty. Let $G={\rm Ung}(D)$, $G_{1}={\rm Ung}(D_{1})$, and $G_{2}$ be the
subgraph of $G$ with $E(G_{2})=E(G)\setminus E(G_{1})$, then
$e(G_{1})=a(D)-2|\mathcal{C}|\leq 17$. Note that $G_{1}$ must be $K_{4}$-free.
We here show that $G_{1}$ has a $C_{4}$-free subgraph $H_{1}$ with
$e(H_{1})>e(G_{1})/2$. If $G_{1}$ is disconnected, then by applying Lemma 4.2
to each (nontrivial) component of $G_{1}$, we can get a required subgraph. If
$G_{1}$ has a vertex $v$ with $d_{G_{1}}(v)\leq 2$, then by Lemma 4.2,
$G_{1}-v$ has a subgraph with edge more than $e(G_{1}-v)/2$, together with an
edge incident to $v$, we get a required subgraphs. Suppose that $G_{1}$ is a
connected graph with $d_{G_{1}}(v)\geq 3$ for all $v\in V(G_{1})$, which
implies $G_{1}$ has two cycles of different lengths, one of which is not a
$C_{4}$. Taking such a cycle, by adding some edges we can get a $C_{4}$-free
subgraph with $9$ edges. Therefore, $G_{1}$ has a $C_{4}$-free subgraph
$H_{1}$ with $e(H_{1})>e(G_{1})/2$. Let $H$ be the subgraph of $G$ with
$E(H)=E(H_{1})\cup E(G_{2})$, then $H$ is a $C_{4}$-free graph with $e(H)\geq
14>{\rm ex}(9,C_{4})=13$ (see [10]), a contradiction. Therefore, we have
$|\mathcal{C}|\leq 4$.

Let $U\subset V(D)$ be the set of vertices that not incident to any
$\overrightarrow{C_{2}}$ in $D$, and $W=V(D)\setminus U$. Since
$|\mathcal{C}|\leq 4$, we have $U\neq\emptyset$. Clearly ${\rm Umg}(D)$ is
connected, otherwise $D$ is not an extremal digraph for
$\overrightarrow{P_{1,3}}$. Thus there exists an edge $u_{1}w_{1}\in E({\rm
Umg}(D))$ with $u_{1}\in U$ and $w_{1}\in W$. Let
$\overrightarrow{C}:=w_{1}w_{2}w_{1}$ be a $\overrightarrow{C_{2}}$ in $D$
with $w_{2}\in W$. If $u_{1},w_{2}$ has a common neighbor other than $w_{1}$
in ${\rm Umg}(D)$, then ${\rm Umg}(D)$ contains a $\varTheta_{1,1,3}$, a
contradiction. Recall that $d_{D}(v)=6$ for all $v\in V(D)$. If
$u_{1}w_{2}\notin E({\rm Umg}(D))$, then $u_{1}$ has at least five neighbors
other than $w_{1}$, and $w_{2}$ has at least two neighbors other than $w_{1}$,
which implyes that $u_{1},w_{2}$ have a common neighbor other than $w_{1}$, a
contradiction. Now we conclude that $u_{1}w_{2}\in E({\rm Umg}(D))$. Thus
$u_{1}$ has at least four neighbors other than $w_{1},w_{2}$. In addition,
$w_{2}$ is contained in another $\overrightarrow{C_{2}}$, say
$w_{2}w_{3}w_{2}$ with $w_{3}\in W\setminus\\{w_{1}\\}$. By the similar
analysis we have that $u_{1}w_{3}\in E({\rm Umg}(D))$. In other words,
$u_{1},w_{1},w_{2},w_{3}$ are contained in a $\varTheta_{1,1,3}$, a
contradiction. Finally, we conclude that $D$ is $\overrightarrow{C_{2}}$-free.
Notice that ${\rm Ung}(D)$ is $K_{4}$-free with $27$ edges, implying that $D$
is an orientation of $T_{9,3}$.

Let $\\{X,Y,Z\\}$ be the balanced partition of ${\rm Umg}(D)$. Fix arbitrary
vertices $x_{0}\in X,y_{0}\in Y,z_{0}\in Z$. By symmetry, we consider the
following two cases: (1) $x_{0}\rightarrow y_{0},y_{0}\rightarrow
z_{0},z_{0}\rightarrow x_{0}$; (2) $x_{0}\rightarrow z_{0},y_{0}\rightarrow
z_{0},y_{0}\rightarrow x_{0}$. Set

$\left\\{\begin{array}[]{lll}X_{1}=X\cap N_{D}^{+}(z_{0}),&Y_{1}=Y\cap
N_{D}^{+}(x_{0}),&Z_{1}=Z\cap N_{D}^{+}(y_{0}),\\\ X_{2}=X\cap
N_{D}^{-}(z_{0}),&Y_{2}=Y\cap N_{D}^{-}(x_{0}),&Z_{2}=Z\cap
N_{D}^{-}(y_{0}),\end{array}\right.\text{ \ for \ }(1)$

and

$\left\\{\begin{array}[]{lll}X_{1}=X\cap N_{D}^{-}(z_{0}),&Y_{1}=Y\cap
N_{D}^{+}(x_{0}),&Z_{1}=Z\cap N_{D}^{-}(y_{0}),\\\ X_{2}=X\cap
N_{D}^{+}(z_{0}),&Y_{2}=Y\cap N_{D}^{-}(x_{0}),&Z_{2}=Z\cap
N_{D}^{+}(y_{0}),\end{array}\right.\text{ \ for \ }(2).$

One can check that the partition $\\{X_{1},X_{2},Y_{1},Y_{2},Z_{1},Z_{2}\\}$
of $V(D)$ satisfies the Properties (i)–(iv) in the definition of
$\overrightarrow{S_{n}}$. Therefore, $D\in\overrightarrow{\mathcal{S}_{9}}$.

Now let $n>9$. For simplicity, set $s(n)=a(\overrightarrow{S_{n}})$, and
assume that ${\rm ex}(n-1,\overrightarrow{P_{1,3}})=s(n-1)$, ${\rm
EX}(n-1,\overrightarrow{P_{1,3}})=\overrightarrow{\mathcal{S}_{n-1}}$. We
first show that every digraph $D$ on $n$ vertices with $a(D)=s(n)+1$ contains
a $\overrightarrow{P_{1,3}}$. If not, then we must have
$d_{D}(v)\geq\lfloor\frac{2s(n)}{n}\rfloor+1$ for every $v\in V(D)$: otherwise
$D^{\prime}=D-v$ is a digraph on $n-1$ vertices with $a(D^{\prime})\geq
s(n-1)+1$, which contains a $\overrightarrow{P_{1,3}}$. Thus, we have

$a(D)=\frac{1}{2}\sum_{v\in
V(D)}d_{D}(v)\geq\frac{n}{2}\left(\left\lfloor\frac{2s(n)}{n}\right\rfloor+1\right)>s(n)+1$

for $n>9$, which contradicts $a(D)=s(n)+1$. Moreover, since all digraphs
$\overrightarrow{S_{n}}$ have no $\overrightarrow{P_{1,3}}$, we get ${\rm
ex}(n,\overrightarrow{P_{1,3}})=s(n)$.

Now let $D\in{\rm EX}(n,\overrightarrow{P_{1,3}})$. We will show that
$D\in\overrightarrow{\mathcal{S}_{n}}$. A simple averaging argument shows that
there exists $v_{0}\in V(D)$ such that
$d_{D}(v_{0})\leq\lfloor\frac{2s(n)}{n}\rfloor$. Set $D^{\prime}:=D-v_{0}$,
then $a(D^{\prime})\geq s(n-1)$ (notice that
$s(n)-s(n-1)=\lfloor\frac{2s(n)}{n}\rfloor$). By the induction hypothesis,
$D^{\prime}$ can only be a graph in $\overrightarrow{\mathcal{S}_{n-1}}$ and
$d_{D}(v_{0})=\lfloor\frac{2s(n)}{n}\rfloor$.

Let $\\{X,Y,Z\\}$ be the (almost balanced) partition of $V(D^{\prime})$. If
$v_{0}$ has neighbors in all the three sets $X,Y,Z$, then ${\rm Ung}(D)$
contains a $K_{4}$ and $D$ contains a $\overrightarrow{P_{1,3}}$, a
contradiction. Therefore we assume without loss of generality that
$X\cup\\{v_{0}\\}$ is independent. Note that
$|X|\geq\lfloor\frac{n-1}{3}\rfloor$. Let $v_{1}$ be an arbitrary vertex in
$X$, then
$d_{D}(v_{1})\leq\lceil\frac{2s(n-1)}{n-1}\rceil\leq\lfloor\frac{2s(n)}{n}\rfloor=d_{D}(v_{0})$,
which implies that $D^{\prime\prime}=D-v_{1}$ is also a digraph in
$\overrightarrow{\mathcal{S}_{n-1}}$, and thus $D$ is an orientation of
$T_{n,3}$. We claim that one of the following statements holds: (1) for every
$u\in Y\cup Z$, $u\rightarrow v_{1}$ if and only if $u\rightarrow v_{0}$; (2)
for every $u\in Y\cup Z$, $u\rightarrow v_{1}$ if and only if
$v_{0}\rightarrow u$. Suppose that neither (1) nor (2) holds. Without loss of
generality there are two vertices $u_{0},u_{1}$, such that $u_{0}\rightarrow
v_{1}$, $u_{0}\rightarrow v_{0}$, $u_{1}\rightarrow v_{1}$ and
$v_{1}\rightarrow u_{2}$, then $D[\\{v_{0},v_{1},u_{0},u_{1}\\}]$ contains a
$\overrightarrow{P_{1,3}}$, a contradiction. Therefore,
$D\in\overrightarrow{\mathcal{S}_{n}}$. ∎

Next we will prove Theorem 1.11 using the transformation between digraph and
balanced bipartite graph. Given a labeled balanced bipartite graph $B=(X,Y;E)$
with $X=\\{x_{i}:i\in[1,n]\\},Y=\\{y_{i}:i\in[1,n]\\}$, let ${\rm Drp}(B)$
denote the digraph with vertex set $V=\\{v_{i}:i\in[1,n]\\}$ and arc set
$A=\\{v_{i}v_{j}:x_{i}y_{j}\in E\\}$. We call ${\rm Drp}(B)$ the directed
representation of $B$. We notice that we also defined the bipartite
representation ${\rm Brp}(D)$ of a digraph $D$ (see the definition before
Theorem 1.11). Clearly, $e({\rm Brp}(D))=a(D)$ for all digraph $D$; and if a
labeled bipartite graph $B$ satisfies $x_{i}y_{i}\notin E(B)$ for all
$i\in[1,n]$, then $a({\rm Drp}(B))=e(B)$.

For $k\in\mathbb{N}^{*}$, an orientation of $C_{2k}$ is called anti-directed
if the orientation of each arc is opposite to that of its predecessor, denoted
by $\overrightarrow{C_{2k}^{a}}$. Note that
$\overrightarrow{K_{2,2}}=\overrightarrow{C_{4}^{a}}$. It is not hard to see
that every $\overrightarrow{C_{2k}^{a}}$ in a digraph $D$ corresponds to a
$C_{2k}$ in its bipartite representation ${\rm Brp}(D)$.

Recall that ${\rm ex}(n,n;C_{2k})$ denote the maximum number of edges in a
$C_{2k}$-free bipartite graph with parts of equal size $n$. By the
construction, it is easy to obtain the following observation.

######  Observation 4.1.

For $n,k\in\mathbb{N}^{*}$ with $k\geq 2$,

${\rm ex}(n,n;C_{2k})-n\leq{\rm ex}(n,\overrightarrow{C_{2k}^{a}})\leq{\rm
ex}(n,n;C_{2k}).$

A perfect matching in a graph is a collection of edges such that every vertex
is contained in exactly one of them. In the proof of the Theorem 1.11, we will
use a famous Hall’s theorem.

######  Theorem 4.1 (Hall [11]).

Let $B$ be a bipartite graph with parts $X$ and $Y$ of equal size. If for
every $U\subseteq X$, $|N_{B}(U)|\geq|U|$, then $B$ contains a perfect
matching.

###### Proof of Theorem 1.11..

For every digraph $D$ and the bipartite representation ${\rm Brp}(D)$, $D$ is
$\overrightarrow{K_{2,2}}$-free if and only if ${\rm Brp}(D)$ is $C_{4}$-free.
This implies that ${\rm ex}(n,\overrightarrow{K_{2,2}})\leq{\rm
ex}(n,n;C_{4})$.

Now let $B=(X,Y;E)$ be an extremal bipartite graph in ${\rm EX}(n,n;C_{4})$
with $n\geq 3$. We claim that there is a label on $V(B)$, say
$X=\\{x_{i}:i\in[n]\\}$, $Y=\\{y_{i}:i\in[n]\\}$, such that $x_{i}y_{i}\notin
E$. Let $\widehat{B}$, the _quasi-complement_ of $B$, be the bipartite graph
on $V(B)$ such that $xy\in E(\widehat{B})$ if and only if $xy\notin E(B)$ for
any $x\in X,y\in Y$. We show that $\widehat{B}$ has a perfect matching.

Suppose that $\widehat{B}$ does not have perfect matching. By Theorem 4.1,
there is a subset $U\subseteq X$ such that $|N_{\widehat{B}}(U)|<|U|$. Since
$|U|\leq n$, we have $|N_{\widehat{B}}(U)|\leq n-1$. If
$|N_{\widehat{B}}(U)|=n-1$, then $U=X$, which implies that there is one vertex
$y^{\prime}\in Y$ such that $N_{\widehat{B}}(y^{\prime})=\emptyset$. Thus
$N_{B}(y^{\prime})=X$. Since $B$ is $C_{4}$-free, we have $|N_{B}(y)|\leq 1$
for every $y\in Y\setminus\\{y^{\prime}\\}$, implying that $e(B)\leq 2n-1$.
Note that $C_{2n}$ is a $C_{4}$-free bipartite graph for $n\geq 3$, implying
$e(B)<{\rm ex}(n,n;C_{4})$, a contradiction. If $|U|=1$, then
$N_{\widehat{B}}(U)=\emptyset$, and we can analysis as above. Now assume that
$|U|\geq 2$ and $|N_{\widehat{B}}(U)|<n-1$, then there are at least two
vertices $y_{1},y_{2}\in Y\setminus N_{\widehat{B}}(U)$. This implies that
$U\subseteq N_{B}(y_{1})\cap N_{B}(y_{2})$. Since $|U|\geq 2$, $B$ contains a
$C_{4}$, a contradiction. Thus we conclude that $\widehat{B}$ has a perfect
matching. Label the vertices of $B$ such that $\\{x_{i}y_{i}:i\in[1,n]\\}$ is
a perfect matching of $\widehat{B}$. The directed representation ${\rm
Drp}(B)$ is a $\overrightarrow{K_{2,2}}$-free digraph with $a({\rm
Drp}(B))={\rm ex}(n,n;C_{4})$. Thus we have ${\rm
ex}(n,\overrightarrow{K_{2,2}})\geq{\rm ex}(n,n;C_{4})$.

Conversely, for every $\overrightarrow{K_{2,2}}$-free extremal digraph $D$, we
can get a $C_{4}$-free graph ${\rm Brp}(D)$ such that $e({\rm
Brp}(D))=a(D)={\rm ex}(n,n;C_{4})$. Therefore, we have
${\rm{EX}}(n,\overrightarrow{K_{2,2}})=\\{D:{\rm
Brp}(D)\in{\rm{EX}}(n,n;C_{4})\\}$ for $n\geq 3$. ∎

To finish this section, we shall prove Lemma 4.2. We make use of the following
results.

######  Theorem 4.2 (Fan [13]).

Let $G$ be a $2$-connected graph of order $n$. If for every two vertices $u,v$
with distance $2$, $\max\\{d(u),d(v)\\}\geq n/2$, then $G$ contains a Hamilton
cycle.

######  Theorem 4.3 (Győri, Keszegh [16]).

Every $K_{4}$-free graph with $n$ vertices and ${\rm ex}(n,K_{3})+t$ edges
contains at least $t$ edge-disjoint triangles.

A graph $G$ is _perfect_ if for every induced subgraph $H$ of $G$,
$\chi(H)=\omega(H)$, where $\chi(H)$ is the chromatic number of $H$ and
$\omega(H)$ is the clique number of $H$.

######  Theorem 4.4 (Chudnovsky et al. [8]).

A graph is perfect if and only if it contains no odd cycle of length at least
five, or its complement, as an induced subgraph.

Now we are ready to prove Lemma 4.2. A _chord_ of a cycle is an edge
connecting two vertices of the cycle but not an edge of the cycle. Given a
cycle $C$ of a graph $G$, for $i\in\mathbb{N}^{*}$, an $i$-chord of $C$ is a
chord $uv$ such that $v$ and $u$ has distance $i$ in $C$; an $i$-bridge of $C$
is a path $P:=uwv$ with $u,v\in V(C)$, $w\notin V(C)$ and $v,u$ has distance
$i$ in $C$.

###### Proof of Lemma 4.2..

For every graph $G$ on $n\leq 3$ vertices, $G$ clearly satisfies the result,
since $G$ is both $K_{4}$-free and $C_{4}$-free. Suppose now there are some
$K_{4}$-free graphs on $4\leq n\leq 8$ vertices that do not satisfy the
result, and choose a counterexample graph $G$ with minimal order. First we
claim $G$ is $2$-connected and $d_{G}(v)\geq 3$ for all $v\in V(G)$. Indeed,
if $G$ is not 2-connected, then each (nontrivial) block $G_{i}$ of $G$
contains a $C_{4}$-free subgraph $H_{i}$ with $e(H_{i})>e(G_{i})/2$. Thus the
union of all such $H_{i}$ form a required subgraph of $G$. Second, if there is
$v\in V(G)$ with $d_{G}(v)=2$, then $G_{1}:=G-v$ has a $C_{4}$-free subgraph
$H_{1}$ with $e(H_{1})>e(G_{1})/2=e(G)/2-1$. Thus the graph $H$ consisting of
$H_{1}$ and one edge incident with $v$ is a required subgraph of $G$.

Next, by considering a longest path and the neighborhood of its end-vertices,
one can see that $G$ has two cycles of different lengths, one of which is not
a $C_{4}$. Taking such a cycle by adding edges we can get a $C_{4}$-free
subgraph $H$ of $G$ with $e(H)=n$, which implies that $e(G)\geq 2n$. Recall
that $G$ is $K_{4}$-free, by Theorem 1.1, we infer that the counterexample
graph $G$ can only be in the following cases: $n=6$ and $e(G)=12$; $n=7$ and
$e(G)\in[14,16]$; or $n=8$ and $e(G)\in[16,21]$.

If $n=6$ and $e(G)=12$, then $G$ can only be the Turán graph $T_{6,3}$.
Clearly $G$ has a $C_{4}$-free subgraph with $7$ edges (see Figure 7).
Similarly, if $n=7$ and $e(G)=16$, then $G$ is also the Turán graph $T_{7,3}$.
One can check that $G$ has a $C_{4}$-free subgraph with $9$ edges (see Figure
7). For $n=7$ and $e(G)=14$ or $15$, by Theorem 4.3 $G$ has two edge-disjoint
triangles. Taking such two triangles by adding edges we can get a $C_{4}$-free
subgraph with 8 edges. So in the following we consider the case $n=8$.

Figure 7. Graphs $T_{6,3}$, $T_{7,3}$, $C_{5}\vee\overline{K_{3}}$, and their
desired $C_{4}$-free subgraphs.

Case A. $e(G)=20$ or 21. In this case we need find a $C_{4}$-free subgraphs
with 11 edges. We only need to deal with the case $e(G)=20$. We claim that $G$
can not contain induced $C_{5}$, $C_{7}$ and $\overline{C_{7}}$. If $G$ has an
induced $C_{7}$, then $e(G)\leq 7+7<20$, a contradiction. If $G$ has an
induced $\overline{C_{7}}$, then $d_{G}(v)\leq 4$ for the vertex $v$ outside
the $\overline{C_{7}}$; for otherwise $G$ contains a $K_{4}$. It follows that
$e(G)\leq 14+4<20$, a contradiction. Furthermore, suppose that $G$ has an
induced $C_{5}$, denoted by $C$. Set $V^{\prime}:=V(G)\setminus V(C)$. If
$e(G[V^{\prime}])=3$, then $|N_{G}(v)\cap V^{\prime}|\leq 2$ for all $v\in
V(C)$, for otherwise $G$ contains a $K_{4}$. It follows that $e(G)\leq
5+10+3<20$, a contradiction. Suppose now $e(G[V^{\prime}])=1$ or 2. Let
$v_{1}v_{2}\in E(G)$ with $v_{1},v_{2}\in V^{\prime}$. Then $|N_{G}(v_{1})\cap
V(C)|+|N_{G}(v_{2})\cap V(C)|\leq 7$; for otherwise $G$ has a $K_{4}$. This
implies that $e(G)\leq 5+2+7+5<20$, a contradiction. Now we suppose
$e(G[V^{\prime}])=0$, then $e(G)\leq 5+15=20$. This implies that $G$ is the
join of $C_{5}$ and $\overline{K_{3}}$. One can check that $G$ has a
$C_{4}$-free subgraph with $11$ edges (see Figure 7). Now we conclude that $G$
has no induced copies of $C_{5},C_{7}$ or $\overline{C_{7}}$.

By Theorem 4.4, we obtain that $G$ is a perfect graph. Recall that $G$ is also
$K_{4}$-free. We have $\chi(G)\leq 3$, i.e., $G$ is a subgraph of a complete
$3$-partite graph $K_{r,s,t}$ with $r+s+t=8$. Note that $e(G)=20\leq
e(K_{r,s,t})=rs+rt+st$. One can compute that $K_{r,s,t}$ can only be
$K_{2,3,3}$ or $K_{2,2,4}$. Thus $G$ is either $K_{2,2,4}$ or one graph
obtained from $K_{2,3,3}$ by removing an edge (there are two non-isomorphic
such graphs). One can check that $G$ has a $C_{4}$-free subgraph with $11$
edges for each case (see Figure 8).

$u$$v$$u$$v$

Figure 8. Graph $K_{2,2,4}$ and the graphs obtained from $K_{2,3,3}$ by
removing one edge $uv$.

Case B. $e(G)=18$ or $19$. In this case we need find a $C_{4}$-free subgraphs
with $10$ edges. We only deal with the case $e(G)=18$. We first show that $G$
contains a Hamilton cycle. Recall that $d_{G}(v)\geq 3$ for all $v\in G$. If
there are two non-adjacent vertices $v_{1},v_{2}\in V(G)$ such that
$d_{G}(v_{1})=d_{G}(v_{2})=3$, then $F:=G[V(G)\setminus\\{v_{1},v_{2}\\}]$ has
$6$ vertex and $12$ edges, which can only be a $T_{6,3}$. It follows that
$G[N_{G}(v_{i})]$ has at least two edges for $i\in[1,2]$. Let $e_{1}\in
E(G[N_{G}(v_{1})])$ and $e_{2}\in E(G[N_{G}(v_{2})])$ such that $e_{1}\neq
e_{2}$. It is easy to check that $T_{6,3}$ has a Hamilton cycle passing
through any two edges (see Figure 9). Let $C^{\prime}$ be a Hamilton cycle of
$F$ passing through $e_{1},e_{2}$. By replacing $e_{1},e_{2}$ with two
1-bridges of $C^{\prime}$ passing through $v_{1},v_{2}$, respectively, we can
get a Hamilton cycle of $G$. If for each two non-adjacent vertices $u,v\in
V(G)$, $\max\\{d(u),d(v)\\}\geq 4$, then $G$ also contains a Hamilton cycle by
Theorem 4.2.

$u_{1}$$v_{1}$$u_{2}$$v_{2}$$u_{1}=u_{2}$$v_{1}$$v_{2}$$u_{1}=u_{2}$$v_{1}$$v_{2}$$u_{1}$$u_{2}$$v_{1}$$v_{2}$

Figure 9. Hamilton cycles of $K_{2,2,2}$ passing through two edges
$u_{1}v_{1},u_{2}v_{2}$.

Let now $C$ be a Hamilton cycle of $G$. Note that $C$ has at most eight
$2$-chords, eight $3$-chords and four $4$-chords. If $C$ has three $2$-chords,
then two of them together with $C$ form a $C_{4}$-free subgraph of $G$ with
$10$ edges. If $C$ has three $4$-chords, then two of them together $C$ form a
$C_{4}$-free subgraph of $G$ with $10$ edges. Therefore, $G$ has at most two
$2$-chords and at most two $4$-chords. In addition, since $e(G)=18$, $C$ has
at least six $3$-chords. Thus $C$ together with six $3$-chords form a subgraph
of $K_{4,4}$ with $14$ edges. Note there are two non-isomorphic subgraph of
$K_{4,4}$ with $14$ edges, each of which has a $\varTheta_{3,3,3}$-subgraph
(see Figure 10). Let $F$ be a $\varTheta_{3,3,3}$-subgraph of $G$ and
$e=v_{1}v_{2}$ be an arbitrary edge in $E(G)\setminus E(F)$. If $v_{1},v_{2}$
have distance in $F$ not equal to $3$, then the subgraph of $G$ obtained from
$F$ by adding the edge $e$ is a $C_{4}$-free graph with $10$ edges. It follows
that every edge in $E(G)\setminus E(F)$ has its two end-vertices with distance
$3$ in $F$. Note that there are exactly $7$ pairs of vertices with distance
$3$ in $F$. Thus we have $e(G)\leq 9+7<18$, a contradiction.

$u_{1}$$v_{1}$$u_{2}$$v_{2}$$u_{1}=u_{2}$$v_{1}$$v_{2}$

Figure 10. Graphs obtained from $K_{4,4}$ by removing two edges
$u_{1}v_{1},u_{2}v_{2}$.

Case C. $e(G)=16$ or 17. In this case we need find a $C_{4}$-free subgraphs
with $9$ edges. We only deal with the case $e(G)=16$. Recall that $G$ is
2-connected and $\delta(G)\geq 3$. Thus $G$ has a cycle of order at least 6.
Let $C$ be a longest cycle of $G$.

If $C$ is a Hamilton cycle, then $C$ has neither $2$-chord nor $4$-chord, for
otherwise $C$ with such a chord form a $C_{4}$-free subgraph of $G$ with $9$
edges. Note that $C$ has at most eight $3$-chords and $e(G)=16$, which implies
that $C$ has all $3$-chords, i.e., $G=K_{4,4}$. Thus $G$ contains a
$\varTheta_{3,3,3}$, which is a $C_{4}$-free subgraph of $G$ with $9$ edges.

Now consider the case $C=C_{7}$. Recall that $d_{G}(v)\geq 3$ for all $v\in
V(G)$. The vertex outside $C$ has three neighbors in $C$. It follows that $C$
has a $1$-bridge or $3$-bridge. Thus $C$ together with such a bridge form a
$C_{4}$-free subgraph of $G$ with $9$ edges.

Finally we assume that $C=C_{6}$. Let $\\{v_{1},v_{2}\\}=V(G)\setminus V(C)$.
Assume first that $v_{1}v_{2}\in E(G)$. Since $d_{G}(v)\geq 3$ for all $v\in
V(G)$, there are two distinct vertices $x_{1},x_{2}\in V(C)$ such that
$v_{1}x_{1},v_{2}x_{2}\in E(G)$. If $x_{1},x_{2}$ has distance $1$ or $2$ in
$C$, then $G$ has a cycle longer than $C$, a contradiction. Thus, the distance
between $x_{1}$ and $x_{2}$ in $C$ has to be $3$. In this case, $C$ together
with edges $v_{1}v_{2},v_{1}x_{1},v_{2}x_{2}$ form a $\varTheta_{3,3,3}$ which
is a required subgraph of $G$. Next, assume that $v_{1}v_{2}\notin E(G)$. For
$i\in[1,2]$, $|N_{G}(v_{i})\cap V(C)|=3$ since $d_{G}(v_{i})\geq 3$ and $C$ is
a longest cycle of $G$. If $C$ has a $2$-chord, then $G$ contains a
$\varTheta_{1,2,4}$. By adding two edges incident to $v_{1},v_{2}$,
respectively, we can get a $C_{4}$-free subgraph of $G$ with $9$ edges. Thus
$C$ has no $2$-chord. Note that $C$ has at most three $3$-chords. We have
$e(G)\leq 6+3+3+3<16$, a contradiction. ∎

##  5 Concluding Remarks

In this paper, we have studied the Turán problem of directed paths, directed
cycles and all orientations of $C_{4}$. In particular, for directed cycles,
our results are exhaustive. Compared with the Turán problem of cycle,
especially even cycles, the Turán problem of directed cycles seems to be
simpler.

However, compared with the Turán problem of paths in graph, we find that the
Turán problem of directed paths is more complex, because the Turán number of
$\overrightarrow{P_{k}}$ is a piecewise function of $n$ and $k$. In extremal
graph theory, this is a very interesting difference between graphs and
digraphs. In deed, for $k+1\leq n\leq 2k-1$, we have ${\rm
ex}(n,\overrightarrow{P_{k+1}})\geq(k-1)(n-1)$ by the following construction:
Let $D$ be the digraph that (i) $V(D)$ has a partition $\\{X,Y\\}$ with
$|X|=k-1$, $|Y|=n-k+1$; (ii) $D[X]$ is complete and $D[Y]$ is empty; (iii)
either $X\mapsto Y$ or $Y\mapsto X$ in $D$. It easy to verify that every $D$
is $\overrightarrow{P_{k+1}}$-free and $a(D)=(k-1)(n-1)$.

In addition, when $2k\leq n\leq 3k-2$, we have the following construction,
which shows that $\overrightarrow{T_{n,k}}$ is not the unique extremal digraph
for $\overrightarrow{P_{k+1}}$ (if it is). Let $D$ be the digraph that: (i)
$V(D)$ has a partition $\\{V_{1},\ldots,V_{t}\\}$ such that $|V_{i}|=3$ or is
even for $i\in[1,t]$; (ii) there are exactly $n-2k$ parts of size 3; (iii)
$D[V_{i}]$ is empty if $|V_{i}|=3$, and
$D[V_{i}]=\overleftrightarrow{2K_{\frac{|V_{i}|}{2}}}$ otherwise; (iv)
$V_{i}\rightarrow V_{j}$ for $1\leq i<j\leq t$. Clearly, $D$ is
$\overrightarrow{P_{k+1}}$-free and $a(D)=a(\overrightarrow{T_{n,k}})$.
Therefore, it is extremely difficult to determine the structure of
$P_{k+1}$-free extremal digraphs for small $n$.

By Theorem 1.5, we already know that every $\overrightarrow{P_{3}}$-free
extremal digraph $D$ belongs to $\overleftrightarrow{\mathcal{T}_{n,2}}$ for
$n\geq 5$. In particular, for $\overrightarrow{P_{4}}$, we can deduce the
following result.

######  Theorem 5.1.

For all $n\geq 9$,

${\rm
ex}(n,\overrightarrow{P_{4}})=a(\overrightarrow{T_{n,3}})=\left\lfloor\frac{n^{2}}{3}\right\rfloor.$

Furthermore,
${\rm{EX}}(n,\overrightarrow{P_{4}})=\overrightarrow{\mathcal{T}_{n,3}}$.

###### Proof.

On one hand, due to $\overrightarrow{T_{n,3}}$ is
$\overrightarrow{P_{4}}$-free, $a(\overrightarrow{T_{n,3}})\leq{\rm
ex}(n,\overrightarrow{P_{4}})$; on the other hand, since
$\overrightarrow{P_{4}}\subset\overrightarrow{P_{1,3}}$ and ${\rm
ex}(n,\overrightarrow{P_{1,3}})=a(\overrightarrow{T_{n,3}})$ for $n\geq 9$, so
we have ${\rm ex}(n,\overrightarrow{P_{4}})=a(\overrightarrow{T_{n,3}})$ for
$n\geq 9$. Furthermore, if $D$ is a $\overrightarrow{P_{4}}$-free digraph of
order $n$ with $a(D)=a(\overrightarrow{T_{n,3}})$, then $D$ is also
$\overrightarrow{P_{1,3}}$-free. This implies that $D\in{\rm
EX}(n,\overrightarrow{P_{1,3}})=\overrightarrow{\mathcal{S}_{n}}$. Clearly a
digraph $\overrightarrow{S_{n}}$ is $\overrightarrow{P_{4}}$-free if and only
if it is in $\overrightarrow{\mathcal{T}_{n,3}}$. we have that
${\rm{EX}}(n,\overrightarrow{P_{4}})=\overrightarrow{\mathcal{T}_{n,3}}$ for
$n\geq 9$. ∎

By Theorem 1.5 and Theorem 5.1, we believe that each
$\overrightarrow{P_{k+1}}$-free extremal digraph belongs to
$\overrightarrow{\mathcal{T}_{n,k}}$ for $n\geq 3k$, and put forward the
following conjecture.

######  Conjecture 5.1.

For every $k,n\in\mathbb{N}^{*}$ with $n\geq 3k$,

${\rm ex}(n,\overrightarrow{P_{k+1}})=a(\overrightarrow{T_{n,k}}),$

and ${\rm EX}(n,\overrightarrow{P_{k+1}})=\overrightarrow{\mathcal{T}_{n,k}}$.

Furthermore, by Observation 4.1, it would be interesting to study the Turán
problem of anti-directed cycles in digraphs. It is well known that the Turán
problems of even cycles in graphs or bipartite graphs have always been
difficult problems in extremal graph theory. For ${\rm ex}(n,n;C_{2k})$ with
$k\geq 2$, it is still a major open question to determine this value, see [25,
30]. In particular, for ${\rm ex}(n,n;C_{4})$, this problem is also a special
case of Zarankiewicz problem. The classical Zarankiewicz problem [32] asks for
the maximum number of edges in a bipartite graph that has a given number of
vertices but has no complete bipartite subgraphs of a given size. Reiman in
1958 [27] showed that if $n=q^{2}+q+1$ where $q$ is the order of a projective
plane (in particular $q$ is a prime power), then ${\rm
ex}(n,n;C_{4})=(q^{2}+q+1)(q+1)$. So far, for general $n$, the precise value
of ${\rm ex}(n,n;C_{4})$ is still an open problem.

The study of Turán problem of anti-directed cycles may provide a good way to
solve the Turán problems of even cycles in bipartite graphs. By Theorem 1.11,
we have already got that ${\rm ex}(n,\overrightarrow{C_{4}^{a}})={\rm
ex}(n,n;C_{4})$ for $n\geq 3$. Therefore, we put forward the following
conjecture.

######  Conjecture 5.2.

For every $k\in\mathbb{N}^{*}$, there exists a constant $n_{0}$ such that for
$n\geq n_{0}$,

${\rm ex}(n,\overrightarrow{C_{2k}^{a}})={\rm ex}(n,n;C_{2k}),$

and ${\rm EX}(n,\overrightarrow{C_{2k}^{a}})=\\{D:{\rm Brp}(D)\in{\rm
EX}(n,n;C_{2k})\\}$.

## Acknowledgements

The authors would like to thank Laihao Ding, Zejun Huang and Miklos Simonovits
for helpful discussion on extremal digraph theory when they were visiting the
School of Mathematics at Shandong University. Part of the work was done while
the second author was visiting the School of Mathematics at Shandong
University. He also thanks Professor Guanghui Wang for the hospitality him
received.

## References

  * [1] S. Ball and V. Pepe.  Asymptotic improvements to the lower bound of certain bipartite turán numbers.  Combin. Probab. Comput., 21(3):323–329, 2012.
  * [2] J. Bang-Jensen and G. Z. Gutin.  Digraphs: theory, algorithms and applications.  Springer Science & Business Media, 2008.
  * [3] B. Bollobás.  Extremal graph theory, in: Handbook of combinatorics, vol. 2.  Elsevier, Amsterdam, 1231–1292, 1995.
  * [4] W. G. Brown, P. Erdős, and M. Simonovits.  Extremal problems for directed graphs.  J. Combin. Theory Ser. B, 15(1):77–93, 1973.
  * [5] W. G. Brown and F. Harary.  Extremal digraphs, combinatorial theory and its applications,  Colloq. Math. Soc. J. Bolyai, 4:135–198, 1970.
  * [6] W. G. Brown and M. Simonovits.  Extremal multigraph and digraph problems.  Paul Erdős and His Mathematics, 2:157–204, 2002.
  * [7] B. Bukh and Z. Jiang.  A bound on the number of edges in graphs without an even cycle.  Combin. Probab. Comput., 26(1):1–15, 2017.
  * [8] M. Chudnovsky, N. Robertson, P.D. Seymour and R.Thomas.  The strong perfect graph theorem.  Ann. of Math. (2), 164:51–229, 2006.
  * [9] F. Chung and L. Lu.  An upper bound for the turán number $t_{3}(n,4)$.  J. Combinatorial Theory, 87(2):381–389, 1999\.
  * [10] C. R. J. Clapham, A. Flockhart, and J. Sheehan.  Graphs without four-cycles.  J. Graph Theory, 13(1):29–47, 1989.
  * [11] R. Diestel.  Graph theory, fifth edition.  Graduate Texts in Mathematics. Springer, Berlin, 2018.
  * [12] P. Erdős and T. Gallai.  On maximal paths and circuits of graphs.  Acta Math. Hungar., 10(3-4):337–356, 1959.
  * [13] G. H. Fan.  New sufficient condition for cycles in graphs.  J. Combin. Theory Ser. B, 37:221–227, 1984.
  * [14] R. J. Faudree and R. H. Schelp.  Path ramsey numbers in multicolorings.  J. Combin. Theory Ser. B, 19(2):150–160, 1975\.
  * [15] F. A. Firke, P. M. Kosek, E. D. Nash, and J. Williford.  Extremal graphs without 4-cycles.  J. Combin. Theory Ser. B, 103(3):327–336, 2013\.
  * [16] E. Győri and B. Keszegh.  On the number of edge-disjoint triangles in $K_{4}$-free graphs.  Combinatorica, 37: 1113–1124, 2017.
  * [17] K. Howalla, A. N. Dabboucy, and R. Tout.  On the maximum number of arcs in some classes of graphs.  Časopis Pěst. Mat., 107(4):388–392, 1982.
  * [18] K. Howalla, A. N. Dabboucy, and R. Tout.  An extremal problem for some classes of oriented graphs.  Časopis Pěst. Mat., 108(1):53–69, 1983.
  * [19] Z. Huang and Z. Lyu.  Extremal digraphs avoiding an orientation of $C_{4}$.  Discrete Math., 343(5):111827, 2020.
  * [20] Z. Huang, Z. Lyu, and P. Qiao.  A turán problem on digraphs avoiding distinct walks of a given length with the same endpoints.  Discrete Math., 342(6):1703–1717, 2019.
  * [21] Z. Huang and X. Zhan.  Digraphs that have at most one walk of a given length with the same endpoints.  Discrete Math., 311(1):70–79, 2011.
  * [22] S. Jukna.  Extremal combinatorics: with applications in computer science, vol. 4.  Springer Science & Business Media, 2011.
  * [23] F. Lazebnik, V. A. Ustimenko, and A. J. Woldar.  Properties of certain families of $2k$-cycle-free graphs.  J. Combin. Theory Ser. B, 60(2):293–298, 1994\.
  * [24] W. Mantel.  Problem 28.  In Wiskundige Opgaven, 10:60–61, 1907.
  * [25] R. Morris and D. Saxton.  The number of $C_{2\ell}$-free graphs.  Adv. Math., 298:534–580, 2016.
  * [26] O. Pikhurko.  A note on the turán function of even cycles.  Proc. Amer. Math. Soc., 140(11):3687–3692, 2012.
  * [27] I. Reiman.  Über ein problem von K. Zarankiewicz.  Acta Math. Hungar., 9(3–4):269–273, 1958.
  * [28] A. Sidorenko.  What we know and what we do not know about turán numbers.  Graphs Combin., 11(2):179–199, 1995.
  * [29] P. Turán.  On an extremal problem in graph theory.  Mat. Fiz. Lapok, 48:436–452, 1941.
  * [30] J. Verstraëte.  Extremal problems for cycles in graphs.  In Recent trends in combinatorics, pages 83–116. Springer, 2016\.
  * [31] Y. Yang and P. Rowlinson.  On extremal graphs without four-cycles.  Util. Math., 41(41):204–210, 1992.
  * [32] K. Zarankiewicz.  Problem 101.  Colloq. Math. 2:301, 1951.