Ore plus Turán

Abstract

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.

43 pages