Extensions of Erd\H{o}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 $\operatorname{ex}_{\mathcal{P}}(n, \mathcal{H}; \delta \geq 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 $\operatorname{EX}_{\mathcal{P}}(n, \mathcal{H}; \delta \geq 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.
이 뉴스, 어떠셨어요?
한 번의 탭으로 반응을 남겨요 · 로그인 불필요