The number of cliques in graphs covered by long cycles

Abstract

Let $G$ be a 2-connected $n$-vertex graph and $N_s(G)$ be the total number of $s$-cliques in $G$. Let $k\ge 4$ and $s\ge 2$ be integers. In this paper, we show that if $G$ has an edge $e$ which is not on any cycle of length at least $k$, then $N_s(G)\le r\left(\genfrac{}{}{0ex}{}{k-1}{s}\right)+\left(\genfrac{}{}{0ex}{}{t+2}{s}\right)$, where $n-2=r(k-3)+t$ and $0\le t\le k-4$. This result settles a conjecture of Ma and Yuan and provides a clique version of a theorem of Fan, Wang and Lv. As a direct corollary, if $N_s(G)>r\left(\genfrac{}{}{0ex}{}{k-1}{s}\right)+\left(\genfrac{}{}{0ex}{}{t+2}{s}\right)$, every edge of $G$ is covered by a cycle of length at least $k$.

arXiv comment7