Article ID Journal Published Year Pages File Type
6874193 Information Processing Letters 2018 5 Pages PDF
Abstract
Let id(v) denote the implicit degree of a vertex v in a graph G. An independent set S of G is said to be essential if S contains a pair of vertices at distance 2 in G. A graph G on n≥3 vertices is called 2-heavy if there exist at least two end-vertices of every induced claw having implicit degree at least n/2. In this paper, we prove that: Let G be a k-connected (k≥2) 2-heavy graph on n≥3 vertices. If max⁡{id(v):v∈S}≥n/2 for every essential independent set S of order k, then G is hamiltonian.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,