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:
-
-
(Preview, Accepted manuscript, pdf, 444.6KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.jctb.2017.03.007
Authors
- 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
- Copyright holder:
- Elsevier Inc
- Copyright date:
- 2017
- Notes:
- © 2017 Elsevier Inc. All rights reserved. This is the accepted manuscript version of the article. The final version is available online from Elsevier at: http://dx.doi.org/10.1016/j.jctb.2017.03.007
If you are the owner of this record, you can report an update to it here: Report update to this record