A Study on Degree Characterization for Hamiltonian-Connected Graphs

Abstract

Consider any undirected and simple graph $G=(V,E)$, where $V$ and $E$ denote the vertex set and the edge set of $G$, respectively. Let $|G|=|V|=n\ge 3$. The well-known Ore’s theorem states that if ${\mathrm{deg}}_G(u)+{\mathrm{deg}}_G(v)\ge n+k$ holds for each pair of nonadjacent vertices $u$ and $v$ of $G$, then $G$ is traceable for $k=-1$, Hamiltonian for $k=0$, and Hamiltonian-connected for $k=1$. In this paper, we investigate any graph $G$ with ${\mathrm{deg}}_G(u)+{\mathrm{deg}}_G(v)\ge n–1$ for any nonadjacent vertex pair $\{u,v\}$ of $G$, in particular. We call it the $(\ast )$ condition. We derive four graph families, ${\mathcal{H}}_i$, $1\le i\le 4$, and prove that all graphs satisfying $(\ast )$ are Hamiltonian-connected unless $G\in \bigcup _{i=1}^4{\mathcal{H}}_i$. We also establish a comprehensive theorem for $G$ satisfying $(\ast )$, which shows that $G$ is traceable, Hamiltonian, pancyclic, or Hamiltonian-connected unless $G$ belongs to different subsets of $\{{\mathcal{H}}_i|1\le i\le 4\}$, respectively.