Implicit degree condition restricted to essential independent sets for Hamiltonian cycles

A cycle of a graph G is Hamiltonian if it visits every vertex of G exactly once. A graph is Hamiltonian if it has a Hamiltonian cycle. The problem of determining whether a graph is Hamiltonian is known to be NP-complete. A subset S of V(G) is called an essential independent set of G if S is an independent set and contains two distinct vertices u and v with a common neighbor. In 1989, Zhu, Li and Deng introduced the definitions of the first implicit degree and the second implicit degree of a vertex v in a graph G, denoted by $$id_1(v)$$ i d 1 ( v ) and $$id_2(v)$$ i d 2 ( v ) , respectively. In this paper, we show that a k-connected ( $$k\ge 2$$ k ≥ 2 ) graph G of order $$n\ge 3$$ n ≥ 3 is Hamiltonian if $$\max \{id_1(v): v\in S\}\ge n/2$$ max { i d 1 ( v ) : v ∈ S } ≥ n / 2 for every essential independent set S of order k and the bound “n/2” is tight, which generalizes the result due to Chen et al. [Essential Independent Sets and Hamiltonian Cycles, J. Graph Theory, 21 (1996) 243–250.].