...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Hamiltonian properties of locally connected graphs with bounded vertex degree
【24h】

Hamiltonian properties of locally connected graphs with bounded vertex degree

机译：有界顶点度的局部连通图的哈密顿性质

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

摘要

We consider the existence of Hamiltonian cycles for the locally connected graphs with a bounded vertex degree. For a graph G, let Δ(G) and δ(G) denote the maximum and minimum vertex degrees, respectively. We explicitly describe all connected, locally connected graphs with Δ(G)4. We show that every connected, locally connected graph with Δ(G)=5 and δ(G)3 is fully cycle extendable which extends the results of Kikust [P.B. Kikust, The existence of the Hamiltonian circuit in a regular graph of degree 5, Latvian Math. Annual 16 (1975) 3338] and Hendry [G.R.T. Hendry, A strengthening of Kikust's theorem, J. Graph Theory 13 (1989) 257260] on full cycle extendability of the connected, locally connected graphs with the maximum vertex degree bounded by 5. Furthermore, we prove that problem Hamilton Cycle for the locally connected graphs with Δ(G)7 is NP-complete.
机译：我们考虑具有有限顶点度的局部连接图的哈密顿环的存在。对于图G，让Δ（G）和δ（G）分别表示最大和最小顶点度。我们用Δ（G）4明确描述所有连通的，局部连通的图。我们表明，每个连接的，局部连接的，具有Δ（G）= 5和δ（G）3的图都是完全循环可扩展的，从而扩展了Kikust [P.B. Kikust，拉脱维亚数学5级正则图中汉密尔顿回路的存在。年刊16（1975）3338]和亨德利[G.R.T. Hendry，Kikust定理的增强，J。图论13（1989）257260]，其最大顶点度为5的连通的局部连通图的全圈可扩展性。此外，我们证明了局部连通的汉密尔顿循环问题Δ（G）7的图是NP完全的。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号