{
  "id": "2406.17371",
  "version": "v1",
  "published": "2024-06-25T08:37:09.000Z",
  "updated": "2024-06-25T08:37:09.000Z",
  "title": "The generalized Tur'{a}n number of long cycles in graphs and bipartite graphs",
  "authors": [
    "Changchang Dong",
    "Mei Lu",
    "Jixiang Meng",
    "Bo Ning"
  ],
  "comment": "19 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a graph $T$ and a family of graphs $\\mathcal{F}$, the maximum number of copies of $T$ in an $\\mathcal{F}$-free graph on $n$ vertices is called the generalized Tur\\'{a}n number, denoted by $ex(n, T , \\mathcal{F})$. When $T= K_2$, it reduces to the classical Tur\\'{a}n number $ex(n, \\mathcal{F})$. Let $ex_{bip}(b,n, T , \\mathcal{F})$ be the maximum number of copies of $T$ in an $\\mathcal{F}$-free bipartite graph with two parts of sizes $b$ and $n$, respectively. Let $P_k$ be the path on $k$ vertices, $\\mathcal{C}_{\\ge k}$ be the family of all cycles with length at least $k$ and $M_k$ be a matching with $k$ edges. In this article, we determine $ex_{bip}(b,n, K_{s,t}, \\mathcal{C}_{\\ge 2n-2k})$ exactly in a connected bipartite graph $G$ with minimum degree $\\delta(G) \\geq r\\ge 1$, for $b\\ge n\\ge 2k+2r$ and $k\\in \\mathbb{Z}$, which generalizes a theorem of Moon and Moser, a theorem of Jackson and gives an affirmative evidence supporting a conjecture of Adamus and Adamus. As corollaries of our main result, we determine $ex_{bip}(b,n, K_{s,t}, P_{2n-2k})$ and $ex_{bip}(b,n, K_{s,t}, M_{n-k})$ exactly in a connected bipartite graph $G$ with minimum degree $\\delta(G) \\geq r\\ge 1$, which generalizes a theorem of Wang. Moreover, we determine $ex(n, K_{s,t}, \\mathcal{C}_{\\ge k})$ and $ex(n, K_{s,t}, P_{k})$ respectively in a connected graph $G$ with minimum degree $\\delta(G) \\geq r\\ge 1$, which generalizes a theorem of Lu, Yuan and Zhang.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-06-25T08:37:09.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "long cycles",
      "generalized tur",
      "minimum degree",
      "connected bipartite graph",
      "maximum number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}