Affordable Access

Maximising the number of induced cycles in a graph

Authors
Type
Preprint
Publication Date
Submission Date
Identifiers
arXiv ID: 1603.02960
Source
arXiv
License
Yellow
External links

Abstract

We determine the maximum number of induced cycles that can be contained in a graph on $n\ge n_0$ 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\ge n_0$ vertices and characterise the extremal graphs. This proves a conjecture of Chv\'atal and Tuza from 1988.

Statistics

Seen <100 times