Maximising the number of induced cycles in a graph
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...
| Prif Awduron: | , |
|---|---|
| Fformat: | Journal article |
| Cyhoeddwyd: |
Elsevier
2017
|
| _version_ | 1826305814571253760 |
|---|---|
| author | Morrison, N Scott, A |
| author_facet | Morrison, N Scott, A |
| author_sort | Morrison, N |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T06:38:33Z |
| format | Journal article |
| id | oxford-uuid:f87e2f79-d911-4bea-b12c-4ee9e185239a |
| institution | University of Oxford |
| last_indexed | 2024-03-07T06:38:33Z |
| publishDate | 2017 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:f87e2f79-d911-4bea-b12c-4ee9e185239a2022-03-27T12:50:40ZMaximising the number of induced cycles in a graphJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:f87e2f79-d911-4bea-b12c-4ee9e185239aSymplectic Elements at OxfordElsevier2017Morrison, NScott, AWe 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. |
| spellingShingle | Morrison, N Scott, A Maximising the number of induced cycles in a graph |
| title | Maximising the number of induced cycles in a graph |
| title_full | Maximising the number of induced cycles in a graph |
| title_fullStr | Maximising the number of induced cycles in a graph |
| title_full_unstemmed | Maximising the number of induced cycles in a graph |
| title_short | Maximising the number of induced cycles in a graph |
| title_sort | maximising the number of induced cycles in a graph |
| work_keys_str_mv | AT morrisonn maximisingthenumberofinducedcyclesinagraph AT scotta maximisingthenumberofinducedcyclesinagraph |