Maximum size of $C_{\le k}$-free strong digraphs with out-degree at least two

Abstract

Let $\mathcal{H}$ be a family of digraphs. A digraph $D$ is \emph{$\mathcal{H}$-free} if it contains no isomorphic copy of any member of $\mathcal{H}$. For $k\ge 2$, we set $C_{\le k}=\{C_2,C_3,\dots ,C_k\}$, where $C_{\ell }$ is a directed cycle of length $\ell \in \{2,3,\dots ,k\}$. Let $D_n^k(\xi ,\zeta )$ denote the family of \emph{$C_{\le k}$-free} strong digraphs on $n$ vertices with every vertex having out-degree at least $\xi$ and in-degree at least $\zeta$, where both $\xi$ and $\zeta$ are positive integers. Let ${\phi }_n^k(\xi ,\zeta )=\max \{|A(D)|:D\in D_n^k(\xi ,\zeta )\}$ and ${\Phi }_n^k(\xi ,\zeta )=\{D\in D_n^k(\xi ,\zeta ):|A(D)|={\phi }_n^k(\xi ,\zeta )\}$. Bermond et al.\;(1980) verified that ${\phi }_n^k(1,1)=\left(\genfrac{}{}{0ex}{}{n-k+2}{2}\right)+k-2$. Chen and Chang\;(2021) showed that $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)-2\le {\phi }_n^3(2,1)\le \left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$. This upper bound was further improved to $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)-1$ by Chen and Chang\;(DAM, 2022), furthermore, they also gave the exact values of ${\phi }_n^3(2,1)$ for $n\in \{7,8,9\}$. In this paper, we continue to determine the exact values of ${\phi }_n^3(2,1)$ for $n\ge 10$, i.e., ${\phi }_n^3(2,1)=\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)-2$ for $n\ge 10$.

21 pages