Extensions of 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$. Erdős proved that when $n\ge 6d$, each nonhamiltonian graph $G$ on $n$ vertices with minimum degree $\delta (G)\ge d$ has at most $h(n,d)$ edges. He also provides a sharpness example $H_{n,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 $\delta (G)\ge d$ and more than $h(n,d+1)$ edges is a subgraph of $H_{n,d}$. In this paper, we show that not only does the graph $H_{n,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 $\delta (G)\ge 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 $\left(\genfrac{}{}{0ex}{}{n-(d+2)}{k}\right)+(d+2)\left(\genfrac{}{}{0ex}{}{d+2}{k-1}\right)$ copies of $K_k$ for any $k$.

arXiv commentEdited 04/05/17 to add another reference