• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International conference on current trends in theory and practice of computer science >Sufficient Conditions for a Connected Graph to Have a Hamiltonian Path
【24h】

Sufficient Conditions for a Connected Graph to Have a Hamiltonian Path

机译：连通图具有哈密顿路径的充分条件

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Let G be a connected graph on n vertices. Let σ_k(G) be the least possible value that is obtained as the sum of the degrees of k pairwise distinct and non-adjacent vertices. We show that if one of the following conditions is satisfied: - σ_3 (G) ≥ n and there is a longest cycle in G which is not a dominating cycle, - σ_2(G) > 2/3 n and G is K_(1,4)-free (i.e. without induced K_(1,4)), - each triple of pairwise non-adjacent vertices contains two vertices u and v such that deg_G(u) + deg_G(v) ≥ n - 1, then G contains a Hamiltonian path.
机译：令G为n个顶点上的连通图。令σ_k（G）是作为k对成对的不相邻顶点的度数之和而获得的最小可能值。我们证明如果满足以下条件之一：-σ_3（G）≥n并且G中存在一个最长的周期，而不是一个主导周期，-σ_2（G）> 2/3 n且G为K_（1 ，4）-free（即没有诱导的K_（1,4）），-每对成对的非相邻顶点包含两个顶点u和v，使得deg_G（u）+ deg_G（v）≥n-1，然后是G包含哈密顿路径。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号