Maximising the Number of Cycles in Graphs with Forbidden Subgraphs

Abstract

Fix $k\ge 2$ and let $H$ be a graph with $\ddot{I}‡(H)=k+1$ containing a critical edge. We show that for sufficiently large $n$, the unique $n$-vertex $H$-free graph containing the maximum number of cycles is $T_k(n)$. This resolves both a question and a conjecture of Arman, Gunderson and Tsaturian.

36 pages