Maximising the number of induced cycles

Maximising the number of induced cycles

-
Alex Scott , Oxford University
Fine Hall 224

How many holes can a graph on n vertices contain?  How many induced cycles? For sufficiently large n, we determine the maximum number of induced cycles, the maximum number of holes, and the maximum number of even or odd induced cycles, and in each case characterize the graphs achieving this bound. This answers a question of Tuza, and a conjecture of Chvatal and Tuza from 1988.  Joint work with Natasha Morrison.