Papers
Topics
Authors
Recent
Search
2000 character limit reached

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

Published 6 Nov 2022 in math.CO | (2211.03129v1)

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$.

Authors (2)

Summary

No one has generated a summary of this paper yet.

Paper to Video (Beta)

No one has generated a video about this paper yet.

Whiteboard

No one has generated a whiteboard explanation for this paper yet.

Open Problems

We haven't generated a list of open problems mentioned in this paper yet.

Continue Learning

We haven't generated follow-up questions for this paper yet.

Collections

Sign up for free to add this paper to one or more collections.