Generalized Zykov's Theorem

For a simple graph $G$, let $n$ denote its number of vertices, and let $N(G,K_t)$ denote the number of copies of $K_t$ in $G$. Zykov’s theorem (1949) asserts that for any $K_{r+1}$-free graph and $t\ge 2$, $$N(G,K_t)\le \left(\genfrac{}{}{0px}{}{r}{t}\right){\left(\frac{n}{r}\right)}^t$$ We generalize Zykov’s bound within a vertex-based localization framework. For each vertex $v\in V(G)$, let $c(v)$ denote the order of the largest clique containing $v$. In this paper, we show that $$N(G,K_t)\le n^{t-1}\sum _{v\in V(G)}\frac{1}{c(v{)}^t}\left(\genfrac{}{}{0px}{}{c(v)}{t}\right)$$ We further show that equality holds if and only if $G$ is a regular complete multipartite graph. \newline Note that if we impose the condition that, $G$ is $K_{r+1}$-free, then $c(v)\le r$ for all $v\in V(G)$. Thus, plugging $c(v)=r$ for all $v\in V(G)$, we retrieve Zykov’s bound.