{
  "id": "2211.03129",
  "version": "v1",
  "published": "2022-11-06T14:20:23.000Z",
  "updated": "2022-11-06T14:20:23.000Z",
  "title": "Maximum size of $C_{\\leq k}$-free strong digraphs with out-degree at least two",
  "authors": [
    "Bin Chen",
    "Xinmin Hou"
  ],
  "comment": "21 pages",
  "categories": [
    "math.CO"
  ],
  "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$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-11-06T14:20:23.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C20",
      "05C35",
      "05C38"
    ],
    "keywords": [
      "free strong digraphs",
      "maximum size",
      "out-degree",
      "exact values",
      "isomorphic copy"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}