The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree

详细信息    查看全文

• 作者：Jonathan Cutler and A. J. Radcliffe
• 刊名：Journal of Graph Theory
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：84
• 期：2
• 页码：134-145
• 全文大小：327K
• ISSN：1097-0118

文摘

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 Δ(G)≤r, which has the most complete subgraphs of size t, for t≥3. The conjectured extremal graph is aKr+1∪Kb, where n=a(r+1)+b with 0≤b≤r. Gan et al. (Combin Probab Comput 24(3) (2015), 521–527) proved the conjecture when a≤1, and also reduced the general conjecture to the case t=3. We prove the conjecture for r≤6 and also establish a weaker form of the conjecture for all r.