The number of edges in graphs with bounded clique number and circumference

Abstract

Let $\mathcal{H}$ be a family of graphs. The Turán number $\mathrm{ex}(n,\mathcal{H})$ is the maximum possible number of edges in an $n$-vertex graph which does not contain any member of $\mathcal{H}$ as a subgraph. As a common generalization of Turán's theorem and Erdős-Gallai theorem on the Turán number of matchings, Alon and Frankl determined $\mathrm{ex}(n,\mathcal{H})$ for $\mathcal{H}=\{K_r,M_k\}$, where $M_k$ is a matching of size $k$. Replacing $M_k$ by $P_k$, Katona and Xiao obtained the Turán number of $\mathcal{H}=\{K_r,P_k\}$ for $r\le \lfloor k/2\rfloor$ and sufficiently large $n$. In addition, they proposed a conjecture for the case of $r\ge \lfloor k/2\rfloor +1$ and sufficiently large $n$. Motivated by the fact that the result for $\mathrm{ex}(n,P_k)$ can be deduced from the one for $\mathrm{ex}(n,{\mathcal{C}}_{\ge k})$, we investigate the Turán number of $\mathcal{H}=\{K_r,{\mathcal{C}}_{\ge k}\}$ in this paper. In other words, we aim to determine the maximum number of edges in graphs with clique number at most $r-1$ and circumference at most $k-1$. For $\mathcal{H}=\{K_r,{\mathcal{C}}_{\ge k}\}$, we are able to show the value of $\mathrm{ex}(n,\mathcal{H})$ for $r\ge \lfloor (k-1)/2\rfloor +2$ and all $n$. As an application of this result, we confirm Katona and Xiao's conjecture in a stronger form. For $r\le \lfloor (k-1)/2\rfloor +1$, we manage to show the value of $\mathrm{ex}(n,\mathcal{H})$ for sufficiently large $n$.

corrected typos