Maximum size of $C_{\leq k}$-free strong digraphs with out-degree at least two
Abstract: Let $\mathscr{H}$ be a family of digraphs. A digraph $D$ is \emph{$\mathscr{H}$-free} if it contains no isomorphic copy of any member of $\mathscr{H}$. For $k\geq2$, we set $C_{\leq k}={C_{2}, C_{3},\ldots,C_{k}}$, where $C_{\ell}$ is a directed cycle of length $\ell\in{2,3,\ldots,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 $\varphi{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)|=\varphi_{n}{k}(\xi,\zeta)}$. Bermond et al.\;(1980) verified that $\varphi_{n}{k}(1,1)=\binom{n-k+2}{2}+k-2$. Chen and Chang\;(2021) showed that $\binom{n-1}{2}-2\leq\varphi_{n}{3}(2,1)\leq\binom{n-1}{2}$. This upper bound was further improved to $\binom{n-1}{2}-1$ by Chen and Chang\;(DAM, 2022), furthermore, they also gave the exact values of $\varphi_{n}{3}(2,1)$ for $n\in {7,8,9}$. In this paper, we continue to determine the exact values of $\varphi_{n}{3}(2,1)$ for $n\ge 10$, i.e., $\varphi_{n}{3}(2,1)=\binom{n-1}{2}-2$ for $n\geq10$.
Paper Prompts
Sign up for free to create and run prompts on this paper using GPT-5.
Top Community Prompts
Collections
Sign up for free to add this paper to one or more collections.