Extremal problems for star forests and cliques

Abstract

Given a family of graphs $\mathcal{F}$, the Turán number $ex(n,\mathcal{F})$ denotes the maximum number of edges in any $\mathcal{F}$-free graph on $n$ vertices. Recently, Alon and Frankl studied of maximum number of edges in an $n$-vertex $\{K_{k+1},M_{s+1}\}$-free graph, where $K_{k+1}$ is a complete graph on $k+1$ vertices and $M_{s+1}$ is a matching of $s+1$ edges. They determined the exact value of $ex(n,\{K_{k+1},M_{s+1}\})$. In this paper, we extend the matching $M_{s+1}$ to star forest $(s+1)S_l$, and determine the exact value of $ex(n,\{K_{k+1},(s+1)S_l\})$ for sufficiently large enough $n$. Furthermore, all the extremal graphs are obtained.