Maximising the number of cycles in graphs with forbidden subgraphs
Fix k≥2 and let H be a graph with χ(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 Tk(n). This resolves both a question and a conjecture of Arman, Gunderson and Tsaturian [4].
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2020
|