An implicit degree condition for k-connected 2-heavy graphs to be hamiltonian

作者：Cai, Junqing^*; Li, Hao; Zhang, Yuzhong

来源：Information Processing Letters, 2018, 134: 9-13.

DOI：10.1016/j.ipl.2018.01.010

• Combinatorial problems
• Implicit degree
• 2-heavy
• Essential independent set
• Hamilton cycle

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 epsilon S} >= n/2 for every essential independent set S of order k, then G is hamiltonian.

• 出版日期2018-6
• 单位曲阜师范大学; 江汉大学