The maximum number of complete subgraphs of fixed size in a graph with given maximum degree

Abstract

In this paper, we make progress on a question related to one of Galvin that has attracted substantial attention recently. The question is that of determining among all graphs $G$ with $n$ vertices and $\Delta (G)\le r$, which has the most complete subgraphs of size $t$, for $t\ge 3$. The conjectured extremal graph is $a{K}_{r+1}\cup K_b$, where $n=a(r+1)+b$ with $0\le b\le r$. Gan, Loh, and Sudakov proved the conjecture when $a\le 1$, and also reduced the general conjecture to the case $t=3$. We prove the conjecture for $r\le 6$ and also establish a weaker form of the conjecture for all $r$.