Degree Sequences and Long Cycles in Graphs
Zh. G. Nikoghosyan · arXiv (Cornell University) · 2017
Let $G$ be a graph on $n$ vertices with degree sequence $\delta=d_1\le d_2\le...\le d_n$. Let $c$ be the circumference - the order of a longest cycle and $p$ the order of a longest path in $G$. In 1952, Dirac proved: (i) every graph with $2d_1\ge n$ is hamiltonian; (ii) in every 2-connected graph, $c\ge \min\{p,2d_1\}$. Recently, the bounds $2d_1\ge n$ and $c\ge \min\{p,2d_1\}$ in (i) and (ii) are improved to $2d_\delta\ge n$ and $c\ge \min\{p,2d_\delta\}$, respectively, by Koulakzian, Mosesyan and Nikoghosyan. In this paper we present two new sharp bounds $d_\delta+d_{\delta+1}\ge n$ and $\min\{2d_{\delta+1},d_\delta+d_{\delta+2}\}\ge n$ instead of $2d_\delta\ge n$, as well as two new sharp bounds $c\ge \min\{p,d_\delta+d_{\delta+1}\}$ and $c\ge \min\{p,2d_{\delta+1},d_\delta+d_{\delta+2}\}$ instead of $c\ge \min\{p,2d_\delta\}$.