Journal article icon

Journal article

Maximising the number of induced cycles in a graph

Abstract:
We determine the maximum number of induced cycles that can be contained in a graph on n ≥ n0 vertices, and show that there is a unique graph that achieves this maximum. This answers a question of Chvátal and Tuza from the 1980s. We also determine the maximum number of odd or even induced cycles that can be contained in a graph on n ≥ n0 vertices and characterise the extremal graphs. This resolves a conjecture of Chvátal and Tuza from 1988.
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1016/j.jctb.2017.03.007

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Role:
Author
More by this author
Institution:
University of Oxford
Oxford college:
Merton College
Role:
Author
Publisher:
Elsevier
Journal:
Journal of Combinatorial Theory, Series B More from this journal
Volume:
126
Pages:
24-61
Publication date:
2017-04-10
Acceptance date:
2017-03-27
DOI:
Pubs id:
pubs:689215
UUID:
uuid:f87e2f79-d911-4bea-b12c-4ee9e185239a
Local pid:
pubs:689215
Source identifiers:
689215
Deposit date:
2017-04-12

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP