English

运筹学学报

• 运筹学 • 上一篇    下一篇

无爪图中不相邻子图P_4和K_1的度和条件下的哈密尔顿性

郑伟1  王力工1,*   

  1. 1. 西北工业大学理学院应用数学系, 西安  710072
  • 收稿日期:2015-01-19 出版日期:2016-03-15 发布日期:2016-03-15
  • 通讯作者: 王力工 lgwangmath@163.com
  • 基金资助:

    国家自然科学基金(No. 11171273)

The Hamilton-connectivity with the degree sum of  non-adjacent subgraphs P_ 4 and K_1 in claw-free graphs

ZHENG Wei1  WANG Ligong1,*   

  1. 1. Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi'an 710072, China
  • Received:2015-01-19 Online:2016-03-15 Published:2016-03-15

PDF

457

摘要：

研究子图的度和图的哈密尔顿性的关系，证明图~$G$ 是一个~$n$ 阶~3-\,连通无爪图且最小度~$\delta(G)\geq4$, 如果图~$G$ 中任意两个分别同构于~$P_4$, $K_1$ 的不相邻子图~$H_1$, $H_2$ 满足~$d(H_1)+d(H_2)\geq n$, 则图~$G$ 是哈密尔顿连通.

关键词: 无爪图, 不相邻子图, 子图的度, 哈密尔顿连通

Abstract:

This paper studies the relationship between the degree of subgraphs and Hamiltonicity of graphs. It is proven that every 3-connected claw-free graph $G$ of order $n$ with minimum degree $\delta(G)\geq4$ is Hamilton-connected if it satisfies $d(H_1)+d(H_2)\geq n$ for any two non-adjacent subgraphs $H_1$, $H_2$ which are isomorphic to $P_4$, $K_1$ respectively.

Key words:  claw-free graph, non-adjacent subgraph, degree of subgraph, Hamilton-connected