Maximizing the density of KtK_t's in graphs of bounded degree and clique number

preprint2020arXivOpen access

Abstract

Zykov showed in 1949 that among graphs on nn vertices with clique number ω(G)≤ωω(G) \le ω, the Turán graph Tω(n)T_ω(n) maximizes not only the number of edges but also the number of copies of KtK_t for each size tt. The problem of maximizing the number of copies of KtK_t has also been studied within other classes of graphs, such as those on nn vertices with maximum degree Δ(G)≤ΔΔ(G) \le Δ. We combine these restrictions and investigate which graphs with Δ(G)≤ΔΔ(G) \le Δ and ω(G)≤ωω(G) \le ω maximize the number of copies of KtK_t per vertex. We define ft(Δ,ω)f_t(Δ,ω) as the supremum of ρtρ_t, the number of copies of KtK_t per vertex, among such graphs, and show for fixed tt and ωω that ft(Δ,ω)=(1+o(1))ρt(Tω(Δ+⌊Δω−1⌋))f_t(Δ,ω) = (1+o(1))ρ_t(T_ω(Δ+\lfloor\fracΔ{ω-1}\rfloor)). For two infinite families of pairs (Δ,ω)(Δ,ω), we determine ft(Δ,ω)f_t(Δ,ω) exactly for all t≥3t\ge 3. For another we determine ft(Δ,ω)f_t(Δ,ω) 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 KtK_t per vertex for every size tt.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.