English

运筹学学报 >

2016 , Vol. 20 >Issue 1: 112 - 117

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2016.01.011

运筹学

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

展开
  • 1. 西北工业大学理学院应用数学系, 西安  710072

收稿日期: 2015-01-19

  网络出版日期: 2016-03-15

基金资助

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

收起

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

Expand
  • 1. Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi'an 710072, China

Received date: 2015-01-19

  Online published: 2016-03-15

Fold

摘要

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

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

本文引用格式

郑伟, 王力工 . 无爪图中不相邻子图P_4和K_1的度和条件下的哈密尔顿性[J]. 运筹学学报, 2016 , 20(1) : 112 -117 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.011

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

参考文献

[1] Bondy J A, Murty U S R. Graph Theory with Applications [M]. New York: Macmillan London and Elsevier, 1976.
[2] Li H. Generalizations of Dirac's theorem in Hamiltonian graph theory: A survey [J]. Discrete Mathematics, 2013, 313: 2034-2053.
[3] Nikoghosyan Z G. Graph invariants and large cycles: A survey [J]. International Journal of Mathematics and Mathematical Sciences, 2011, 2011: 1-11.
[4] 马修山. 子图的度与若干图类的路圈问题 [D]. 济南: 山东师范大学, 2013.
[5] 米晶. 特殊图类路圈性质的子图度型充分条件研究 [D].  济南: 山东师范大学, 2014.
[6] 孙运伟. 图的路圈性质的子图度型充分条件研究 [D]. 济南: 山东师范大学, 2014.
[7] 徐珊珊, 王江鲁. 子图的度与Hamilton 圈 [J]. 山东师范大学学报, 2012, 27(4): 13-14.
[8] 米晶, 王江鲁. 无爪图中子图的度和与Hamilton 连通性 [J]. 应用数学进展, 2014, 3(1): 8-16.
Options
文章导航

/

〈 〉