|Table of Contents|

[1] Zhou Xiaoyue*, Huang Yuenian,. Hamilton Graphs Involving Connectivity [J]. Journal of Southeast University (English Edition), 2001, 17 (2): 78-80. [doi:10.3969/j.issn.1003-7985.2001.02.019]
Copy

Hamilton Graphs Involving Connectivity()
包含连通度的Hamilton图
Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:
17
Issue:
2001 2
Page:
78-80
Research Field:
Mathematics, Physics, Mechanics
Publishing date:
2001-12-30

Info

Title:
Hamilton Graphs Involving Connectivity
包含连通度的Hamilton图
Author(s):
Zhou Xiaoyue1*;  Huang Yuenian2
1Nanjing Architectural and Civil Engineering Institute, Nanjing 210009, China
2Jinling Petrochemical Design Institute, Nanjing 210042, China
周小跃;  黄月年
南京建筑工程学院, 南京 210009) (金陵石油化工设计院, 南京 210042
Keywords:
connectivity;  independent set;  Hamilton graph
连通度;  独立集;  Hamilton图
PACS:
O157.5
DOI:
10.3969/j.issn.1003-7985.2001.02.019
Abstract:
Let G be a 2-connected simple graph of order n and connectivity k.Bauer, Broersma and Li proved that for an independent set S={u, v, w}, d(u)+d(v)+d(w)≥n+k, then G is Hamiltonian. This paper improves the result.Let S be an independent set. If there exist u, v∈S, d(u, v)=2, then S is called a 2-independent set. This paper proves the following result. Let G be a simple graph of order n and connectivity k≥2. If for every 2-independent set S={u, v, w}, d(u)+d(v)+d(w)≥n+k, then G is Hamiltonian. This result implies that we may consider all triples of 2-independent set instead of all triples of independent set.
设G是一个2-连通简单图, 具有阶n和连通度k.Bauer 等人已证明:如果对任意三点独立集S={u, v, w}, 都有d(u)+d(v)+d(w)≥n+k, 则G是Hamilton图.本文改进了这个结果.如果一个独立集S中存在距离为2的2点, 则称S是一个2-独立集.本文证明了如下结果:如果对任意3点2-独立集S={u, v, w}, 都有d(u)+d(v)+d(w)≥n+k.则G是Hamilton图.这个结果意味我们仅需要检查所有2-独立集是否满足条件.

References:

[1] J.A. Bondy, and U.S.R. Murty, Graph theory with a applications, Macmillan Press, London, 1976
[2] D.Bauer, H.J.Broersma, and R. Li, et al., A generalization of a result of haggkvist and nicoghossian, J Comb Theory, B, no.47, pp.237-243, 1989
[3] B.Wei, A short proof of a theorem concerning degree sums and connectivity on Hamilon graphs, J Comb Theory, B, no.75, pp.157-159, 1999
[4] G.Fan, New sufficient conditions for cycles in graphs, J Comb Theory, B, no.37, pp.221-227, 1984

Memo

Memo:
* Born in 1958, female, lecturer.
Last Update: 2001-06-20