Forbidden Subgraph Conditions for Hamilton Cycles in Implicit Claw-Heavy Graphs

Abstract

Let \(id(v)\) denote the implicit degree of a vertex \(v\) in a graph \(G\). We define \(G\) to be implicit claw-heavy if every induced claw of \(G\) has a pair of nonadjacent vertices such that their implicit degree sum is more than or equal to \(|V(G)|\). In this paper, we show that an implicit claw-heavy graph \(G\) is hamiltonian if we impose certain additional conditions on \(G\) involving numbers of common neighbors of some specific pair of nonadjacent vertices, or forbidden induced subgraphs. Our results extend two previous theorems of Chen et al. [B. Chen, 8. Zhang and S. Qiao, Hamilton cycles in claw-heavy graphs, Discrete Math., \(309 (2009) 2015-2019.]\) on the existence of Hamilton cycles in claw-heavy graphs.