2017/03/29 by Zoltán Füredi, Füredi, Zoltán, Alexandr Kostochka +3
Computer Science · Mathematics · #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.1703.10268
openalex publication_date 2017/03/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let n, d be integers with 1 ≤ d ≤ \lfloor (n-1)/(2) \rfloor, and set h(n,d):=n-d \choose 2 + d2. Erdős proved that when n ≥ 6d, each nonhamiltonian graph G on n vertices with minimum degree δ(G) ≥ d has at most h(n,d) edges. He also provides a sharpness example Hn,d for all such pairs n,d. Previously, we showed a stability version of this result: for n large enough, every nonhamiltonian graph G on n vertices with δ(G) ≥ d and more than h(n,d+1) edges is a subgraph of Hn,d. In this paper, we show that not only does the graph Hn,d maximize the number of edges among nonhamiltonian graphs with n vertices and minimum degree at least d, but in fact it maximizes the number of copies of any fixed graph F when n is sufficiently large in comparison with d and |F|. We also show a stronger stability theorem, that is, we classify all nonhamiltonian n-graphs with δ(G) ≥ d and more than h(n,d+2) edges. We show this by proving a more general theorem: we describe all such graphs with more than n-(d+2) \choose k + (d+2)d+2 \choose k-1 copies of Kk for any k.