• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete mathematics >A note on powers of Hamilton cycles in generalized claw-free graphs
【24h】

A note on powers of Hamilton cycles in generalized claw-free graphs

机译：关于广义无爪图中Hamilton圈的幂的注记

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Seymour conjectured for a fixed integer k ≥ 2 that if G is a graph of order n with δ(G) ≥ kn/(k + 1), then G contains the kth power Ck n of a Hamiltonian cycle Cn of G, and this minimum degree condition is sharp. Earlier the k = 2 case was conjectured by Pósa. This was verified by Komlós et al. [4]. For s ≥ 3, a graph is K1,s-free if it does not contain an induced subgraph isomorphic to K1,s. Such graphs will be referred to as generalized clawfree graphs. Minimum degree conditions that imply that a generalized claw-free graph G of sufficiently large order n contains a kth power of a Hamiltonian cycle will be proved. More specifically, it will be shown that for any ε> 0 and for n sufficiently large, any K1,s-free graph of order n with δ(G) ≥ (1/2 + ε)n contains a Ckn.
机译：对于固定整数k≥2的西摩猜想，如果G是阶数为n的图，且δ（G）≥kn /（k + 1），则G包含G的哈密顿循环Cn的第k次幂Ck n，并且最低学位条件是尖锐的。早前k = 2的案例是由Pósa猜想的。 Komlós等人对此进行了验证。 [4]。对于s≥3，如果图不包含与K1，s同构的诱导子图，则该图是无K1，s的。这样的图将被称为广义无爪图。将证明暗示足够大阶数的广义无爪图G包含哈密顿循环的k次方的最小程度条件。更具体地说，将显示出，对于任何ε> 0和足够大的n，任何具有δ（G）≥（1/2 +ε）n的n阶的无K1，s无图都包含Ckn。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号