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

Abstract

Zykov showed in 1949 that among graphs on $n$ vertices with clique number $\omega (G)\le \omega$, the Turán graph $T_{\omega }(n)$ maximizes not only the number of edges but also the number of copies of $K_t$ for each size $t$. The problem of maximizing the number of copies of $K_t$ has also been studied within other classes of graphs, such as those on $n$ vertices with maximum degree $\Delta (G)\le \Delta$. We combine these restrictions and investigate which graphs with $\Delta (G)\le \Delta$ and $\omega (G)\le \omega$ maximize the number of copies of $K_t$ per vertex. We define $f_t(\Delta ,\omega )$ as the supremum of ${\rho }_t$, the number of copies of $K_t$ per vertex, among such graphs, and show for fixed $t$ and $\omega$ that $f_t(\Delta ,\omega )=(1+o(1)){\rho }_t(T_{\omega }(\Delta +\lfloor \frac{\Delta }{\omega -1}\rfloor ))$. For two infinite families of pairs $(\Delta ,\omega )$, we determine $f_t(\Delta ,\omega )$ exactly for all $t\ge 3$. For another we determine $f_t(\Delta ,\omega )$ exactly for the two largest possible clique sizes. Finally, we demonstrate that not every pair $(\Delta ,\omega )$ has an extremal graph that simultaneously maximizes the number of copies of $K_t$ per vertex for every size $t$.

References in corpus (1)

• Maximizing the number of independent sets of a fixed size

Cited by in corpus (1)

• Maximizing Cliques in Shellable Clique Complexes