Implicit Degree Sum Condition for Hamiltonian Cycles

Abstract

The Hamiltonian problem is a classical problem in graph theory. Most of the research on the Hamiltonian problem is looking for sufficient conditions for a graph to be Hamiltonian. For a vertex $v$ of a graph $G$, Zhu, Li, and Deng introduced the concept of implicit degree $id(v)$, according to the degrees of its neighbors and the vertices at distance $2$ with $v$ in $G$. In this paper, we will prove that: Let $G$ be a $2$-connected graph on $n\ge 3$ vertices. If the maximum value of the implicit degree sums of $2$ vertices in $S$ is more than or equal to $n$ for each independent set $S$ with $\kappa (G)+1$ vertices, then $G$ is Hamiltonian.