An Algorithm for Hamiltonian Cycles under Implicit Degree Conditions

Abstract

In 1989, Zhu, Li, and Deng introduced the definition of implicit degree, denoted by \(\text{id}(v)\), of a vertex \(v\) in a graph \(G\). In this paper, we give a simple method to prove that: if \(G\) is a \(k\)-connected graph of order \(n\) such that the implicit degree sum of any \(k+1\) independent vertices is more than \((k+1)(n-1)/2\), then \(G\) is hamiltonian. Moreover, we provide an algorithm according to the proof.