Maximising the Number of Cycles in Graphs with Forbidden Subgraphs

2019/02/21 by Morrison, Natasha, Roberts, Alexander, Scott, Alex
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1902.08133

Abstract

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 T_k(n). This resolves both a question and a conjecture of Arman, Gunderson and Tsaturian.

Related

• Maximising the number of induced cycles in a graph
• The maximum number of cycles in a graph with fixed number of edges
• On the number of cycles in a graph with restricted cycle lengths
• Forbidden subgraphs and complete partitions
• Exact results for generalized extremal problems forbidding an even cycle