2014/05/06 by Jonathan Cutler, Cutler, Jonathan, A. J. Radcliffe +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1405.1322
openalex publication_date 2014/05/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Δ(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, Loh, and Sudakov 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.