Long cycles in graphs through fragments

Abstract

Four basic Dirac-type sufficient conditions for a graph $G$ to be hamiltonian are known involving order $n$, minimum degree $\delta$, connectivity $\kappa$ and independence number $\alpha$ of $G$: (1) $\delta \ge n/2$ (Dirac); (2) $\kappa \ge 2$ and $\delta \ge (n+\kappa )/3$ (by the author); (3) $\kappa \ge 2$ and $\delta \ge \max \{(n+2)/3,\alpha \}$ (Nash-Williams); (4) $\kappa \ge 3$ and $\delta \ge \max \{(n+2\kappa )/4,\alpha \}$ (by the author). In this paper we prove the reverse version of (4) concerning the circumference $c$ of $G$ and completing the list of reverse versions of (1)-(4): (R1) if $\kappa \ge 2$, then $c\ge \min \{n,2\delta \}$ (Dirac); (R2) if $\kappa \ge 3$, then $c\ge \min \{n,3\delta -\kappa \}$ (by the author); (R3) if $\kappa \ge 3$ and $\delta \ge \alpha$, then $c\ge \min \{n,3\delta -3\}$ (Voss and Zuluaga); (R4) if $\kappa \ge 4$ and $\delta \ge \alpha$, then $c\ge \min \{n,4\delta -2\kappa \}$. To prove (R4), we present four more general results centered around a lower bound $c\ge 4\delta -2\kappa$ under four alternative conditions in terms of fragments. A subset $X$ of $V(G)$ is called a fragment of $G$ if $N(X)$ is a minimum cut-set and $V(G)-(X\cup N(X))\ne \varnothing$.

32 pages