Extremal digraphs containing at most $t$ paths of length 2 with the same endpoints

Abstract

Given a positive integer $t$, let $P_{t,2}$ be the digraph consisting of $t$ directed paths of length 2 with the same initial and terminal vertices. In this paper, we study the maximum size of $P_{t+1,2}$-free digraphs of order $n$, which is denoted by $ex(n,P_{t+1,2})$. For sufficiently large $n$, we prove that $ex(n,P_{t+1})=g(n,t)$ when $\lfloor (n-t)/2\rfloor$ is odd and $ex(n,P_{t+1,2})\in \{g(n,t)-1,g(n,t)\}$ when $\lfloor (n-t)/2\rfloor$ is even, where $g(n,t)=\lceil (n+t)/2\rceil \lfloor (n-t)/2\rfloor +tn+1$.