Maximizing the density of Kt’s in graphs of bounded degree and clique number

• Published in: Discrete mathematics 2020-06, Vol.343 (6), Article 111803
• Main Authors: Kirsch, R., Radcliffe, A.J.
• Format: Article
• Language: English
• Subjects: Clique number; Cliques; Extremal enumerative problems; Maximum degree
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2019.111803

Zykov showed in 1949 that among graphs on n vertices with clique number ω(G)≤ω, the Turán graph Tω(n) maximizes not only the number of edges but also the number of copies of Kt for each size t. The problem of maximizing the number of copies of Kt has also been studied within other classes of graphs, such as those on n vertices with maximum degree Δ(G)≤Δ. We combine these restrictions and investigate which graphs with Δ(G)≤Δ and ω(G)≤ω maximize the number of copies of Kt per vertex. We define ft(Δ,ω) as the supremum of ρt, the number of copies of Kt per vertex, among such graphs, and show for fixed t and ω that ft(Δ,ω)=(1+o(1))ρt(Tω(Δ+⌊Δω−1⌋)). For two infinite families of pairs (Δ,ω), we determine ft(Δ,ω) exactly for all t≥3. For another we determine ft(Δ,ω) exactly for the two largest possible clique sizes. Finally, we demonstrate that not every pair (Δ,ω) has an extremal graph that simultaneously maximizes the number of copies of Kt per vertex for every size t.