Ore plus Turán

2023/10/17 by Aleyah Dawkins, Dawkins, Aleyah, Rachel Kirsch +1
Computer Science · Mathematics · #05C35 #05C45 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2310.11452

openalex publication_date 2023/10/17 · openalex created_date 2023/10/20 · openalex updated_date 2026/07/28

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.

Related

• Maximizing the number of stars in graphs with forbidden properties
• A variation of a theorem by Pósa
• A note on the number of edges in a Hamiltonian graph with no repeated cycle length
• Graphs with Many Hamiltonian Paths
• Many Hamiltonian subsets in large graphs with given density