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

Abstract

Let $n,d$ be integers with $1\le d\le \lfloor \frac{n-1}{2}\rfloor$, and set $h(n,d):=\left(\genfrac{}{}{0ex}{}{n-d}{2}\right)+d^2$ and $e(n,d):=\max \{h(n,d),h(n,\lfloor \frac{n-1}{2}\rfloor )\}$. Because $h(n,d)$ is quadratic in $d$, there exists a $d_0(n)=(n/6)+O(1)$ such that $e(n,1)>e(n,2)>\cdots >e(n,d_0)=e(n,d_0+1)=\cdots =e(n,\lfloor \frac{n-1}{2}\rfloor )$. A theorem by Erdős states that for $d\le \lfloor \frac{n-1}{2}\rfloor$, any $n$-vertex nonhamiltonian graph $G$ with minimum degree $\delta (G)\ge d$ has at most $e(n,d)$ edges, and for $d>d_0(n)$ the unique sharpness example is simply the graph $K_n-E(K_{\lceil (n+1)/2\rceil })$. Erdős also presented a sharpness example $H_{n,d}$ for each $1\le d\le d_0(n)$. We show that if $d<d_0(n)$ and a $2$-connected, nonhamiltonian $n$-vertex graph $G$ with $\delta (G)\ge d$ has more than $e(n,d+1)$ edges, then $G$ is a subgraph of $H_{n,d}$. Note that $e(n,d)-e(n,d+1)=n-3d-2\ge n/2$ whenever $d<d_0(n)-1$.

Edited 04/05/17 to add a new reference

Cited by in corpus (1)

• A variation of a theorem by Pósa