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 \geq 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.