A stability version for a theorem of Erdős on nonhamiltonian graphs

Füredi, Zoltán and Kostochka, A. and Luo, Ruth (2017) A stability version for a theorem of Erdős on nonhamiltonian graphs. DISCRETE MATHEMATICS, 340 (11). pp. 2688-2690. ISSN 0012-365X

Preview

Text 1608.05741v2.pdf Download (267kB) | Preview

Abstract

Let n,d be integers with 1≤d≤[Formula presented], and set h(n,d)≔[Formula presented]+d2 and e(n,d)≔max{h(n,d),h(n,[Formula presented])}. Because h(n,d) is quadratic in d, there exists a d0(n)=(n∕6)+O(1) such that e(n,1)>e(n,2)>⋯>e(n,d0)=e(n,d0+1)=⋯=en,[Formula presented].A theorem by Erdős states that for d≤[Formula presented], any n-vertex nonhamiltonian graph G with minimum degree δ(G)≥d has at most e(n,d) edges, and for d>d0(n) the unique sharpness example is simply the graph Kn−E(K⌈(n+1)∕2⌉). Erdős also presented a sharpness example Hn,d for each 1≤d≤d0(n). We show that if d<d0(n) and a 2-connected, nonhamiltonian n-vertex graph G with δ(G)≥d has more than e(n,d+1) edges, then G is a subgraph of Hn,d. Note that e(n,d)−e(n,d+1)=n−3d−2≥n∕2 whenever d<d0(n)−1. © 2016 Elsevier B.V.

Actions (login required)

Edit Item