Maximising the number of induced cycles in a graph

Natasha Morrison, Alex Scott

Published 2016-03-09Version 1

We determine the maximum number of induced cycles that can be contained in a graph on $n\ge n_0$ vertices. We characterise the $n$-vertex graphs that contain this maximum number of cycles, showing that they are unique up to isomorphism. We also determine the maximum number of odd or even cycles that can be contained in a graph on $n\ge n_0$ vertices and characterise the extremal graphs.