Extremal digraphs avoiding distinct walks of length 3 with the same endpoints

The Turán-type extremal problem is an important topics in extremal graph theory, which concerns the maximum number of edges in graphs containing no given subgraphs and the extremal graphs achieving this maximum. Most of the previous results on Turán problems concern undirected graphs and only a few Turán problems on digraphs have been investigated; see [2, 4, 5, 8, 9, 14, 15] and the references therein.

A simple digraph is a digraph that does not contain multiple arcs but allows loops. A strict digraph is a loopless simple digraph. Digraphs in this paper are simple unless otherwise stated. We follow the terminology and notations in [1]. Directed walks, directed paths and directed cycles are abbreviate as walks, paths and cycles, respectively. The number of vertices in a digraph is called its order and the number of arcs its size. Given a digraph $D$ and a set of digraphs $F$, $D$ is said to be $F$-free if $D$ contains no digraph in $F$ as its subgraph.

Denote by $\overrightarrow{K}_{n}$ the complete digraph on $n$ vertices. A natural Turán problem on digraphs is determining the maximum size of $\overrightarrow{K}_{r}$-free digraphs of a given order, which has been solved in [12]. Brown and Harary [4] determined the precise extremal size of digraphs as well as the extremal digraphs that avoids a tournament. They also studied digraphs avoiding a direct sum of two tournaments, or a digraph on at most 4 vertices where any two vertices are joined by at least one arc. In [9], we determined the extremal size of digraphs avoiding an orientation of the 4-cycle as well as the extremal digraphs. By adopting dense matrices, Brown, Erdős, and Simonovits [2, 3] presented asymptotic results on extremal digraphs avoiding a family of digraphs. Howalla, Dabboucy and Tout [6, 7] determined the extremal sizes of the $\overrightarrow{K}_{2}$-free digraphs avoiding $k$ paths with the same initial vertex and terminal vertex for $k=2,3$. Maurer, Rabinovitch and Trotter [14] studied the extremal $\overrightarrow{K}_{2}$-free transitive digraphs which contain at most one path from $x$ to $y$ for any two distinct vertices $x,y.$

Denote by $F_{k}$ the family of digraphs consisting of two different walks of length $k$ with the same initial vertex and the same terminal vertex. Let $ex(n,F_{k})$ be the maximum size of $F_{k}$-free digraphs of order $n$, and let $EX(n,F_{k})$ be the set of $F_{k}$-free digraphs of order $n$ with size $ex(n,F_{k})$. We are interested in the following Turán -type problem.

Let $D=(V,{A})$ be a digraph with vertex set ${V}=\{v_{1},v_{2},\ldots,v_{n}\}$ and arc set ${A}$. Its adjacency matrix $A_{D}=(a_{ij})$ is defined by

$$a_{ij}=\left\{\begin{array}[]{ll}1,&\textrm{if }(v_{i},v_{j})\in{A};\\ 0,&\textrm{otherwise}.\end{array}\right.$$

(1.1)

Conversely, given an 0-1 matrix $A=(a_{ij})_{n\times n}$, we can define its digraph $D(A)=({V},{A})$ on vertices $v_{1},v_{2},\ldots,v_{n}$ by (1.1), whose adjacency matrix is $A$. Considering the entries of $A^{k}(D)$, Problem 1 is equivalent to the following matrix problem, which was proposed by X. Zhan in 2007; see [17, p.234].

Problem 1’. Determine the maximum number of ones in a 0-1 matrix $A$ of order $n$ such that $A^{k}$ is also a 0-1 matrix. Characterize the extremal 0-1 matrices attaining this maximum.

In 2010, Wu [16] solved Problem 1 for the case $k=2$. Huang and Zhan [11] solved the case $k\geq n-1\geq 4$ and determined $ex(k+2,F_{k})$, $ex(k+3,F_{k})$ when $k\geq 4$. Huang, Lyu and Qiao [10] determined $ex(n,F_{k})$ for $4\leq k\leq n-4$, and characterized $EX(n,F_{k})$ for $5\leq k\leq n-4$. They also characterize $EX(k+2,F_{k})$ and $EX(k+3,F_{k})$ when $k\geq 4$. Lyu [13] characterized $EX(n,F_{4})$ when $n\geq 8$. In this paper, we solve the last remained case $k=3$ when $n\geq 16$.

To state our results, we need the following notations and definitions. For a digraph $D=(V,A)$, we denote by $a(D)$ the size of $D$. For $i,j\in V$, if $D$ contains an arc from $i$ to $j$, we say that $j$ is a successor of $i$, and $i$ is a predecessor of $j$, denoted $ij$ or $i\rightarrow j$. A directed walk $xv_{1}v_{2}\cdots v_{k}y$ is called a $xy$-walk, where $x$ is its initial vertex and $y$ is its terminal vertex. For $S,T\subset V$, we denote by $D[S]$ the subgraph of $D$ induced by $S$, $A(S,T)$ the set of arcs from $S$ to $T$, $a(S,T)$ the cardinality of $A(S,T)$. Let

$$N^{+}(u)=\{x\in V|ux\in A\}\quad\text{and}\quad N^{-}(u)=\{x\in V|xu\in A\}$$

be the out-neighbour set and in-neighbour set a vertex $u$, respectively. The out-degree and in-degree of $u$ are $d^{+}(u)\equiv|N^{+}(u)|$ and $d^{-}(u)\equiv|N^{-}(u)|$, respectively. Let $\Delta^{+}(D)$ denote the maximum out-degree of $D$, which are abbreviate as $\Delta^{+}$ if there is no confusion. Given $X\subseteq V$, $d^{+}_{X}(u)$ and $d^{-}_{X}(u)$ are the numbers of the successors and predecessors of $u$ from $X$, respectively.

Two digraphs $D_{1}=(V_{1},A_{1})$ and $D_{2}=(V_{2},A_{2})$ are isomorphic, written $D_{1}\cong D_{2}$, if there is a bijection $\sigma:V_{1}\rightarrow V_{2}$ such that $(u,v)\in A_{1}$ if and only if $(\sigma(u),\sigma(v))\in A_{2}$.

For a digraph $D=(V,A)$ with $V=\{v_{1},v_{2},\ldots,v_{n}\}$, a blow-up of $D$ is obtained by replacing every vertex $v_{i}$ with a finite collection of copies of $v_{i}$, denoted $V_{i}$, so that $xy$ is an arc for $x\in V_{i}$ and $y\in V_{j}$ if and only if $v_{i}v_{j}\in A(D)$. A blow-up of a digraph is said to be balanced if $|V_{i}|$ and $|V_{j}|$ differ by at most one for any pair $i\neq j$. Denote by $B(V_{1},V_{2})$ the blow-up of an arc with vertex set $V_{1}\cup V_{2}$ such that $xy$ is an arc in $B(V_{1},V_{2})$ if and only if $x\in V_{1},y\in V_{2}$, and $T(V_{1},V_{2},V_{3})$ the blow-up of the transitive tournament of order 3 such that $xy$ is an arc in $T(V_{1},V_{2},V_{3})$ if and only if $x\in V_{i},y\in V_{j}$ with $i<j$.

Given a digraph $D$, denote by $D+e$ the digraph obtained from $D$ by adding an arc $e$, where the arc $e$ is allowed to be a loop. We define $H(V_{1},V_{2})$ to be the digraph obtained from $B(V_{1},V_{2})$ by adding an arc or a loop with both ends from $V_{1}$. Let

	$\displaystyle T_{3,n}=$	$\displaystyle\{$	$\displaystyle T(V_{1},V_{2},V_{3})+e:|V_{1}|+|V_{2}|+|V_{3}|=n,|V_{i}|=\left\lfloor\frac{n}{3}\right\rfloor~{}{\rm or}~{}\left\lceil\frac{n}{3}\right\rceil~{}{\rm for}~{}i=1,2,3,$
			$\displaystyle e\text{ is an arc with both ends from }V_{2}\},$

which is the set of digraphs obtained from a balanced blow-up of the transitive tournament of order 3 by embedding an arc in the middle partite set. Then each digraph in $T_{3,n}$ has one of the diagrams in Figure 1.

Now we state our main result as follows.

Notice that $T_{3,n}$ contains some loopless digraphs. By Theorem 2 we have the following result for strict digraphs.

Remark. Combining Theorem 2 with previous results, we now obtain a full solution to Problem 1 (Problem 1’).

We will need the following lemmas to prove Theorem 2.

Now we are ready to present the proof of Theorem 2.

Proof of Theorem 2. Let $D\in T_{3,n}$. Then $D=T(V_{1},V_{2},V_{3})+e$ with $|V_{i}|=\lfloor{n}/{3}\rfloor$ or $\lceil{n}/{3}\rceil~{}{\rm for}~{}i=1,2,3,$ and $e$ is an arc with both ends from $V_{2}$. It is clear that all walks in $D$ have length $\leq 3$. Moreover, for any walk $v_{1}v_{2}v_{3}v_{4}$ of length 3, we have $v_{2}v_{3}=e$. Therefore, there are no two distinct walks of length 3 with the same initial vertex and the same terminal vertex, i.e., $D$ is $F_{3}$-free. Hence,

$$ex(n,F_{3})\geq a(D)=\left\lfloor\frac{n^{2}}{3}\right\rfloor+1.$$

(2.7)

Now let $D=(V,A)\in EX(n,F_{3})$. Suppose $v_{0}$ is a vertex with $d^{+}(v_{0})=\Delta^{+}$. It follows from (2.7) that

$$\Delta^{+}\geq\left\lfloor\frac{n}{3}\right\rfloor+1.$$

(2.8)

Let $V_{1}=N^{+}(v_{0})$ and $V_{2}=V\setminus V_{1}$. We count $a(D)$ in the following way:

$$a(D)=a(V_{1},V_{1})+a(V_{1},V_{2})+a(V_{2},V)=a(V_{1},V_{1})+\sum\limits_{u\in V_{2}}[d^{+}(u)+d^{-}_{V_{1}}(u)].$$

(2.9)

For any $u\in V_{2}$, if $d^{-}_{V_{1}}(u)\geq 2$, then $d^{+}(u)=0$ as $D$ is $F_{3}$-free. Therefore,

$$d^{+}(u)+d^{-}_{V_{1}}(u)\leq\Delta^{+}+1$$

(2.10)

for all $u\in V_{2}$. Moreover, equality in (2.10) holds only if $d^{+}(u)=\Delta^{+}$ and $d^{-}_{V_{1}}(u)=1$. Now we prove the following claim.

Claim 1. $d^{+}(u)+d^{-}_{V_{1}}(u)\leq\Delta^{+}$ for all $u\in V_{2}$.

Proof of Claim 1. We first assert that there are at most two vertices in $V_{2}$ satisfying the equality in (2.10). Suppose otherwise there are three vertices $u_{1},u_{2},u_{3}\in V_{2}$ satisfying the equality in (2.10). Then we have

$$d^{-}_{V_{1}}(u_{1})=d^{-}_{V_{1}}(u_{2})=d^{-}_{V_{1}}(u_{3})=1$$

and

$$d^{+}(u_{1})=d^{+}(u_{2})=d^{+}(u_{3})=\Delta^{+}.$$

Hence, there are $u_{1}^{\prime},u_{2}^{\prime},u_{3}^{\prime}\in V_{1}$ such that $\{u_{1}^{\prime}u_{1},u_{2}^{\prime}u_{2},u_{3}^{\prime}u_{3}\}\subseteq A$. By (2.8), there are two vertices in $\{u_{1},u_{2},u_{3}\}$ sharing a common successor. Without loss of generality, we assume $u_{1}\rightarrow u$ and $u_{2}\rightarrow u$. Then $D$ contains the walks $v_{0}\rightarrow u_{1}^{\prime}\rightarrow u_{1}\rightarrow u$ and $v_{0}\rightarrow u_{2}^{\prime}\rightarrow u_{2}\rightarrow u$, a contradiction.

Since $D$ is $F_{3}$-free and $V_{1}$ is the out-neighbour set of $v_{0}$, $D[V_{1}]$ does not contain two distinct walks of length 2 with a common terminal vertex. Applying Lemma 4 on $D[V_{1}]$, we have

$$a(D[V_{1}])=a(V_{1},V_{1})\leq\left\lfloor\frac{(\Delta^{+})^{2}}{4}\right\rfloor+1.$$

Combining this with (2.7) and (2.9), we obtain

$$\left\lfloor\frac{(\Delta^{+})^{2}}{4}\right\rfloor+\Delta^{+}(n-\Delta^{+})+3\geq a(D)\geq\left\lfloor\frac{n^{2}}{3}\right\rfloor+1,$$

which leads to

$$\frac{(\Delta^{+})^{2}}{4}+\Delta^{+}(n-\Delta^{+})+3\geq\frac{n^{2}}{3}.$$

It follows that

$$\left\lceil\frac{2n}{3}\right\rceil-2\leq\Delta^{+}\leq\left\lfloor\frac{2n}{3}\right\rfloor+2.$$

(2.11)

Suppose that there are $u_{1},u_{2}\in V_{2}$ such that

$$d^{+}(u_{1})+d^{-}_{V_{1}}(u_{1})=d^{+}(u_{2})+d^{-}_{V_{1}}(u_{2})=\Delta^{+}+1.$$

Then $d^{+}(u_{1})=d^{+}(u_{2})=\Delta^{+}$ and $d^{-}_{V_{1}}(u_{1})=d^{-}_{V_{1}}(u_{2})=1$, which implies that there are $u_{1}^{\prime},u_{2}^{\prime}\in V_{1}$ such that $\{u_{1}^{\prime}u_{1},u_{2}^{\prime}u_{2}\}\subseteq A$. By (2.11), $u_{1}$ and $u_{2}$ share a common successor $u$. Therefore, $D$ contains the walks $v_{0}\rightarrow u_{1}^{\prime}\rightarrow u_{1}\rightarrow u$ and $v_{0}\rightarrow u_{2}^{\prime}\rightarrow u_{2}\rightarrow u$, a contradiction.

Note that $\Delta^{+}(n-\Delta^{+})+\left\lfloor(\Delta^{+})^{2}/4\right\rfloor$ is the size of a complete 3-partite (undirected) graph on $n$ vertices and $\left\lfloor n^{2}/3\right\rfloor$ is the size of a balanced 3-partite complete (undirected) graph on $n$ vertices. We always have

$$\left\lfloor n^{2}/3\right\rfloor\geq\Delta^{+}(n-\Delta^{+})+\left\lfloor(\Delta^{+})^{2}/4\right\rfloor.$$

(2.12)

Suppose there is only one vertex $u\in V_{2}$ satisfying the equality in (2.10). Then we get

$$d^{+}(u)=\Delta^{+}.$$

(2.13)

Moreover, $u$ has exactly one predecessor $w$ in $V_{1}$. By (2.7), (2.9), (2.10) and (2.12), we get

	$\displaystyle a(V_{1},V_{1})$	$\displaystyle=$	$\displaystyle a(D)-\sum\limits_{u\in V_{2}}[d^{+}(u)+d^{-}_{V_{1}}(u)]$
		$\displaystyle\geq$	$\displaystyle\left\lfloor\frac{n^{2}}{3}\right\rfloor-\Delta^{+}(n-\Delta^{+})$
		$\displaystyle\geq$	$\displaystyle\left\lfloor\frac{(\Delta^{+})^{2}}{4}\right\rfloor.$

Therefore, we have either

$$a(V_{1},V_{1})=\left\lfloor\frac{(\Delta^{+})^{2}}{4}\right\rfloor+1$$

(2.14)

or

$$a(V_{1},V_{1})=\left\lfloor\frac{(\Delta^{+})^{2}}{4}\right\rfloor.$$

(2.15)

If (2.14) holds, then $D[V_{1}]$ isomorphic to $H(U_{1},U_{2})$ with $\{|U_{1}|,|U_{2}|\}=\{\lfloor\Delta^{+}/2\rfloor,\lceil\Delta^{+}/2\rceil\}$. If (2.15) holds, applying Corollary 5 on $D[V_{1}]$, $D[V_{1}]$ is isomorphic to a digraph obtained from $H(U_{1},U_{2})$ with $\{|U_{1}|,|U_{2}|\}=\{\lfloor\Delta^{+}/2\rfloor,\lceil\Delta^{+}/2\rceil\}$ by deleting an arbitrary arc, or $D=H(U_{1},U_{2})$ with $\{|U_{1}|,|U_{2}|\}=\left\{\Delta^{+}/2-1,\Delta^{+}/2+1\right\}$ provided $\Delta^{+}$ is even. In all the above cases, there is a subset of $V_{1}$ with cardinality $\lceil\Delta^{+}/2\rceil-1$, say $V_{3}$, in which any pair of vertices has a common successor in $V_{1}$.

Since $D$ is $F_{3}$-free, $u$ has at most one successor in $V_{3}$. Now $n\geq 16$, $d^{+}(u)=\Delta^{+}$ and (2.11) enforce that $u$ has at least three successors $u_{1},u_{2},u_{3}$ in $V_{2}$. On the other hand, we assert that there is at most one vertex $v\in V_{2}$ such that

$$d^{+}(v)+d^{-}_{V_{1}}(v)\leq\Delta^{+}-1.$$

Otherwise we have

	$\displaystyle a(D)$	$\displaystyle=$	$\displaystyle a(V_{1},V_{1})+\sum\limits_{v\in V_{2}}[d^{+}(v)+d^{-}_{V_{1}}(v)]$
		$\displaystyle\leq$	$\displaystyle\left(\left\lfloor\frac{(\Delta^{+})^{2}}{4}\right\rfloor+1\right)+(n-\Delta^{+})\Delta^{+}-1$
		$\displaystyle<$	$\displaystyle\left\lfloor\frac{n^{2}}{3}\right\rfloor+1,$

a contradiction. Hence, two of $u_{1},u_{2},u_{3}$, say $u_{1}$ and $u_{2}$, satisfy $d^{+}(u_{i})+d^{-}_{V_{1}}(u_{i})\geq\Delta^{+}-1$. It follows that $d^{+}(u_{i})\geq\Delta^{+}-2$ for $i=1,2$. Since $u_{1}$ and $u_{2}$ have at most one successor in $V_{3}$, they have a common successor $x$. Therefore, $D$ contains the walks $w\rightarrow u\rightarrow u_{1}\rightarrow x$ and $w\rightarrow u\rightarrow u_{2}\rightarrow x$, a contradiction.

Therefore, there is no vertex $u$ in $V_{2}$ such that the equality in (2.12) holds. This completes the proof of Claim 1. ∎

By Claim 1, (2.9) and (2.12), we get

	$\displaystyle a(D)$	$\displaystyle=$	$\displaystyle a(V_{1},V_{1})+\sum\limits_{u\in V_{2}}[d^{+}(u)+d^{-}_{V_{1}}(u)]$		(2.16)
		$\displaystyle\leq$	$\displaystyle\left\lfloor\frac{(\Delta^{+})^{2}}{4}\right\rfloor+1+(n-\Delta^{+})\Delta^{+}$
		$\displaystyle\leq$	$\displaystyle\left\lfloor\frac{n^{2}}{3}\right\rfloor+1.$		(2.17)

Combining this with (2.7), we have

$$ex(n,F_{3})=a(D)=\left\lfloor\frac{n^{2}}{3}\right\rfloor+1.$$

(2.18)

Now we characterize the structure of $D$. The equality (2.18) implies that (2.16) and (2.17) are both equalities. The equality in (2.17) leads to

$$\Delta^{+}=\left\{\begin{array}[]{ll}2n/3,&\text{if }n\equiv 0\text{ (mod 3)};\\ \lfloor 2n/3\rfloor\text{ or }\lfloor 2n/3\rfloor+1,&\text{otherwise}.\\ \end{array}\right.$$

(2.19)

The equality in (2.16) implies

$$a(V_{1},V_{1})=\left\lfloor\frac{(\Delta^{+})^{2}}{4}\right\rfloor+1$$

and

$$d^{+}(u)+d^{-}_{V_{1}}(u)=\Delta^{+}\quad\text{for all}\quad u\in V_{2}.$$

Applying Lemma 4 on $D[V_{1}]$, $D[V_{1}]$ is isomorphic to $H(V_{3},V_{4})$ with $\{|V_{3}|,|V_{4}|\}=\{\lfloor\Delta^{+}/2\rfloor,$ $\lceil\Delta^{+}/2\rceil\}$.

Next we prove

$$a(V_{1},V_{2})=0.$$

(2.20)

If there is a vertex $u\in V_{2}$ such that $d^{-}_{V_{1}}(u)\geq 2$, then $u$ has no successor, which implies $d^{-}_{V_{1}}(u)=\Delta^{+}$. Therefore, all vertices in $V_{4}$ are predecessors of $u$. Choose any $u_{1},u_{2}\in V_{3}$ and $u_{3}\in V_{4}$. We find two walks $v_{0}\rightarrow u_{1}\rightarrow u_{3}\rightarrow u$ and $v_{0}\rightarrow u_{2}\rightarrow u_{3}\rightarrow u$ in $D$, a contradiction. Therefore, we have

$$d^{-}_{V_{1}}(u)\leq 1\quad\text{and}\quad d^{+}(u)\geq\Delta^{+}-1\quad\text{for all}\quad u\in V_{2}.$$

(2.21)

Suppose $d^{-}_{V_{1}}(u)=1$ with $w$ being the predecessor of $u$ in $V_{1}$. Then $d^{+}(u)=\Delta^{+}-1$. We assert that $u$ has at most one successor in $V_{3}$. Otherwise if $u$ has two successors $u_{1},u_{2}$ in $V_{3}$, then $D$ contains two walks $w\rightarrow u\rightarrow u_{1}\rightarrow u_{3}$ and $w\rightarrow u\rightarrow u_{2}\rightarrow u_{3}$ for any $u_{3}\in V_{4}$, a contradiction. By (2.21), $u$ has at least two successors in $V_{2}$, say $u_{1}$ and $u_{2}$, which have a common successor $u_{3}$. Then $D$ contains two walks $w\rightarrow u\rightarrow u_{1}\rightarrow u_{3}$ and $w\rightarrow u\rightarrow u_{2}\rightarrow u_{3}$, a contradiction. Therefore, we have

$$d^{-}_{V_{1}}(u)=0\quad\text{and}\quad d^{+}(u)=\Delta^{+}\quad\text{for all}\quad u\in V_{2},$$

(2.22)

and (2.20) holds.

Finally, we assert

$$a(V_{2},V_{2})=0.$$

(2.23)

Otherwise suppose $u_{1}u_{2}\in A(D[V_{2}])$. If $u_{2}$ has two successors in $V_{2}$, say $u_{3}$ and $u_{4}$, by (2.19) and (2.22), $u_{3}$ and $u_{4}$ share a common successor $u_{5}$. Then $D$ contains two walks $u_{1}\rightarrow u_{2}\rightarrow u_{3}\rightarrow u_{5}$ and $u_{1}\rightarrow u_{2}\rightarrow u_{4}\rightarrow u_{5}$, a contradiction. If $u_{2}$ has two successors $u_{3},u_{4}\in V_{3}$, then those successors share a common successor $u_{5}$ in $V_{4}$, and $D$ also contains the above walks, a contradiction again. It follows that

$$d^{+}(u_{2})\leq|V_{2}|+2<\Delta^{+},$$

which contradicts (2.22). Hence, we have (2.23).

By (2.20), (2.22) and (2.23), we see that $D[V_{2}]$ is an empty digraph and all vertices in $V_{1}$ are successors of $u$ for all $u\in V_{2}$. Therefore, $D=T(V_{2},V_{3},V_{4})+e\in T_{3,n}$, where both ends of the arc $e$ are from $V_{3}$. This completes the proof. ∎

This work was supported by Science and Technology Foundation of Shenzhen City (No. JCYJ20190808174211224)