Article ID Journal Published Year Pages File Type
427321 Information Processing Letters 2014 4 Pages PDF
Abstract

•We impose implicit degree conditions on forbidden induced subgraphs.•A 2-connected graph is hamiltonian if it is implicit claw-heavy, P6-free.•The result in this paper is stronger than Chen's et al. in some sense.

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 at least |V(G)||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 forbidden induced subgraphs. Our result extends a previous theorem of Chen et al. (2009) [6] on the existence of hamiltonian cycles in claw-heavy graphs.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,