Generalized Turán problem for a path and a clique

Abstract

Let $\mathcal{H}$ be a family of graphs. The generalized Turán 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.