Maximising the number of induced cycles in a graph

2016/03/09 by Morrison, Natasha, Scott, Alex · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1603.02960

Abstract

We determine the maximum number of induced cycles that can be contained in a graph on n≥ n₀ vertices, and show that there is a unique graph that achieves this maximum. This answers a question of Tuza. We also determine the maximum number of odd or even cycles that can be contained in a graph on n≥ n₀ vertices and characterise the extremal graphs. This resolves a conjecture of Chvátal and Tuza from 1988.

Cited by

• Edge inducibility via local directed graphs

Related

• The maximum number of cycles in a graph with fixed number of edges
• The maximum number of induced C₅'s in a planar graph
• On the maximum number of odd cycles in graphs without smaller odd cycles
• Maximising the Number of Cycles in Graphs with Forbidden Subgraphs
• On the number of cycles in a graph with restricted cycle lengths