错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Local Degree Conditions for Hamiltonicity of Claw-Free Graphs

  • Wangyi Shang,
  • Shenggui Zhang,
  • Binlong Li,
  • Xia Liu

摘要

Let G be a 2-connected claw-free graph on n vertices. For a vertex \(v\in V(G)\) v V ( G ) and an integer \(r\ge 1\) r 1 , \(M^r(v)\) M r ( v ) denotes the set of vertices of G whose distances from v do not exceed r. Matthews and Sumner in 1985 proved that G is hamiltonian if \(d(v)\ge \frac{n-2}{3}\) d ( v ) n - 2 3 for every vertex \(v\in V(G)\) v V ( G ) . In this paper we pay attention to localize the above Matthews-Sumner’s degree condition by determining the minimum integer r such that G is hamiltonian if \(d(v)\ge \frac{|M^r(v)|-2}{3}\) d ( v ) | M r ( v ) | - 2 3 for every vertex \(v\in V(G)\) v V ( G ) . While we conjecture that \(r=3\) r = 3 is best possible, we settle the case \(r=4\) r = 4 . In fact, we obtain a strong result that G is hamiltonian if \(d(v)\ge \frac{|M^4(v)|-2}{3}\) d ( v ) | M 4 ( v ) | - 2 3 for every vertex v that is an end-vertex of an induced copy of a net, which is a graph obtained from a triangle by adding three disjoint pendant edges. This generalizes a result of Chen which states that G is hamiltonian if \(d(v)\ge \frac{n-2}{3}\) d ( v ) n - 2 3 for every vertex v that is an end-vertex of an induced copy of a net.