Further results on the number of cliques in graphs covered by long cycles

Leilei Zhang

paper

Further results on the number of cliques in graphs covered by long cycles

arXiv:2309.06087

Abstract

Let $Γ (n, k)$ be the set of $2$ -connected $n$ -vertex graphs containing an edge that is not on any cycle of length at least $k + 1.$ Let $g_{s} (n, k)$ denote the maximum number of $s$ -cliques in a graph in $Γ (n, k) .$ Recently, Ji and Ye [SIAM J. Discrete Math., 37 (2023) 917-924] determined $g_{s} (n, k) .$ They remark that it is interesting to characterize the extremal graphs. In this paper, we give such a characterization.

13 pages. Comments welcome!