...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >Pancyclicity of Hamiltonian and highly connected graphs
【24h】

Pancyclicity of Hamiltonian and highly connected graphs

机译：哈密​​顿图和高连通图的泛循环性

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

摘要

A celebrated theorem of Chvátal and Erdo{double acute}s says that G is Hamiltonian if κ(G)>α(G), where κ(G) denotes the vertex connectivity and α(G) the independence number of G. Moreover, Bondy suggested that almost any non-trivial conditions for Hamiltonicity of a graph should also imply pancyclicity. Motivated by this, we prove that if κ(G)>600α(G) then G is pancyclic. This establishes a conjecture of Jackson and Ordaz up to a constant factor. Moreover, we obtain the more general result that if G is Hamiltonian with minimum degree δ(G)>600α(G) then G is pancyclic. Improving an old result of Erdo{double acute}s, we also show that G is pancyclic if it is Hamiltonian and n>150α(G)3. Our arguments use the following theorem of independent interest on cycle lengths in graphs: if δ(G)>300α(G) then G contains a cycle of length ? for all 3
机译：Chvátal和Erdo {double急性} s的一个著名定理说，如果κ（G）>α（G），则G是哈密顿量，其中κ（G）表示顶点连通性，而α（G）表示G的独立数。邦迪建议，图的汉密尔顿性的几乎所有非平凡条件也应暗示泛环性。由此证明，如果κ（G）>600α（G），则G为泛环。这就建立了杰克逊和奥尔达兹的猜想，直到一个恒定的因子。此外，我们得到了更普遍的结果，如果G是最小度δ（G）>600α（G）的哈密顿量，则G是全环。改善Erdo {double急性} s的旧结果，我们还表明，如果G是哈密顿量且n>150α（G）3，则它是泛环的。我们的论点在图中使用以下关于周期长度的独立关注定理：如果δ（G）>300α（G），则G包含一个长度为？的周期。对于所有3 ＜δ＜δ（G）/ 81。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号