Ore plus Turán
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912466662850560 |
|---|---|
| author | Dawkins, Aleyah Kirsch, Rachel |
| author_facet | Dawkins, Aleyah Kirsch, Rachel |
| contents | Ore in 1961 determined the maximum number of edges in graphs not containing a Hamiltonian cycle, and Turán in 1941 found the maximum number of edges in graphs not containing a $K_{r+1}$. Motivated by the work of Adamus in 2009 and Ferrero and Lesniak in 2018 on the maximum number of edges in $r$-partite non-Hamiltonian graphs, we find the maximum number of edges in $K_{r+1}$-free non-Hamiltonian graphs. Then we extend this result from Hamiltonicity to traceability, chorded pancyclicity, Hamiltonian-connectedness, $k$-path Hamiltonicity, $k$-Hamiltonicity, $k$-Hamiltonian-connectedness, and $k$-connectedness. Finally we introduce a method for translating results on the maximum number of edges to results on the maximum number of $t$-cliques using the fact that colex Turán graphs are extremal, and thus determine the maximum number of $t$-cliques in each of these classes of graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_11452 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Ore plus Turán Dawkins, Aleyah Kirsch, Rachel Combinatorics 05C35, 05C45 Ore in 1961 determined the maximum number of edges in graphs not containing a Hamiltonian cycle, and Turán in 1941 found the maximum number of edges in graphs not containing a $K_{r+1}$. Motivated by the work of Adamus in 2009 and Ferrero and Lesniak in 2018 on the maximum number of edges in $r$-partite non-Hamiltonian graphs, we find the maximum number of edges in $K_{r+1}$-free non-Hamiltonian graphs. Then we extend this result from Hamiltonicity to traceability, chorded pancyclicity, Hamiltonian-connectedness, $k$-path Hamiltonicity, $k$-Hamiltonicity, $k$-Hamiltonian-connectedness, and $k$-connectedness. Finally we introduce a method for translating results on the maximum number of edges to results on the maximum number of $t$-cliques using the fact that colex Turán graphs are extremal, and thus determine the maximum number of $t$-cliques in each of these classes of graphs. |
| title | Ore plus Turán |
| topic | Combinatorics 05C35, 05C45 |
| url | https://arxiv.org/abs/2310.11452 |