Implicit Degree Condition for Hamiltonicity of Graphs

Abstract

In order to find more sufficient conditions for the existence of hamiltonian cycles of graphs, Zhu, Li, and Deng proposed the definition of implicit degree of a vertex. In this paper, we consider the relationship between implicit degrees of vertices and the hamiltonicity of graphs, and obtain that: If the implicit degree sum for each pair of nonadjacent vertices of an induced claw or an induced modified claw in a \(2\)-connected graph \(G\) is more than or equal to \(|V(G)| – 1\), then \(G\) is hamiltonian with some exceptions. This extends a previous result of Cai et al. [J. Cai, H. Li and W. Ning, An implicit degree condition for hamiltonian cycles, Ars Combin. \(108 (2013) 365-378.]\) on the existence of hamiltonian cycles.