Generalized Turán Problem with Bounded Matching Number

Abstract

For a graph $T$ and a set of graphs $\mathcal{H}$, let $\mbox{ex}(n,T,\mathcal{H})$ denote the maximum number of copies of $T$ in an $n$-vertex $\mathcal{H}$-free graph. Recently, Alon and Frankl [Journal of Combinatorial Theory, Series B, 2024] determined the exact value of $\mbox{ex}(n,K_2,\{K_{k+1},M_{s+1}\})$, where $K_{k+1}$ and $M_{s+1}$ are complete graph on $k+1$ vertices and matching of size $s+1$, respectively. In this paper, we continue the study of the function $\mbox{ex}(n, T,\{K_{k+1},M_{s+1}\})$. We determine the exact value of $\mbox{ex}(n,K_r,\{K_{k+1},M_{s+1}\})$ for $r\ge 3$ and the exact value of $\mbox{ex}(n,S_r,\{K_{k+1},M_{s+1}\})$ for $n\ge 2(s+1)(r+1)$ and $r\ge 2$.