The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree
Jonathan Cutler, A. J. Radcliffe · Journal of Graph Theory · 2016
Abstract In this article, 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 , which has the most complete subgraphs of size t , for . The conjectured extremal graph is , where with . Gan et al. (Combin Probab Comput 24(3) (2015), 521–527) proved the conjecture when , and also reduced the general conjecture to the case . We prove the conjecture for and also establish a weaker form of the conjecture for all r .