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

Jonathan Cutler, A. J. Radcliffe

Published 2014-05-06Version 1

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)\leq r$, which has the most complete subgraphs of size $t$, for $t\geq 3$. The conjectured extremal graph is $aK_{r+1}\cup K_b$, where $n=a(r+1)+b$ with $0\leq b\leq r$. Gan, Loh, and Sudakov proved the conjecture when $a\leq 1$, and also reduced the general conjecture to the case $t=3$. We prove the conjecture for $r\leq 6$ and also establish a weaker form of the conjecture for all $r$.