Extensions of Erdős's 1962 theorem on non-Hamiltonian graphs

Abstract

For a positive integer $k$, a graph property $\mathcal{H}$, and a graph parameter $\mathcal{P}$, let ${\mathrm{ex}}_{\mathcal{P}}(n,\mathcal{H};\hat{I}´\ge k)$ denote the maximum value of $\mathcal{P}$ over all $n$-vertex graphs with minimum degree at least $k$ that do not possess the property $\mathcal{H}$. The corresponding extremal families are denoted by ${\mathrm{EX}}_{\mathcal{P}}(n,\mathcal{H};\hat{I}´\ge k)$. For two disjoint graphs $H_1$ and $H_2$, let $H_1\cup H_2$ denote their disjoint union, and let $H_1\vee H_2$ denote their join. In 1962, Erdős established a classical theorem on the maximum number of edges in a non-Hamiltonian graph with prescribed order and minimum degree. Motivated by recent work on feasible graph parameters in \cite{ALNS2023}, we prove several extensions of Erdős's 1962 theorem on non-Hamiltonian graphs. The first result gives a common generalization of the extremal theorem due to Erdős and its spectral analogues. As direct applications, we obtain complete solutions to open problems raised in the literature since 2016, thereby improving nearly all related prior results in this direction.

We extend the notions of feasible parameters and weakly feasible parameters to general graphs (including disconnected graphs)several months ago