{
  "id": "2409.10129",
  "version": "v1",
  "published": "2024-09-16T09:43:08.000Z",
  "updated": "2024-09-16T09:43:08.000Z",
  "title": "Generalized Turán problem for a path and a clique",
  "authors": [
    "Xiaona Fang",
    "Xiutao Zhu",
    "Yaojun Chen"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\mathcal{H}$ be a family of graphs. The generalized Tur\\'an number $ex(n, K_r, \\mathcal{H})$ is the maximum number of copies of the clique $K_r$ in any $n$-vertex $\\mathcal{H}$-free graph. In this paper, we determine the value of $ex(n, K_r, \\{P_k, K_m \\} )$ for sufficiently large $n$ with an exceptional case, and characterize all corresponding extremal graphs, which generalizes and strengthens the results of Katona and Xiao [EJC, 2024] on $ex(n, K_2, \\{P_k, K_m \\} )$. For the exceptional case, we obtain a tight upper bound for $ex(n, K_r, \\{P_k, K_m \\} )$ that confirms a conjecture on $ex(n, K_2, \\{P_k, K_m \\} )$ posed by Katona and Xiao.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-09-16T09:43:08.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "generalized turán problem",
      "exceptional case",
      "tight upper bound",
      "corresponding extremal graphs",
      "free graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}