|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()
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
Author(s):
Zhou Xiaoyue1* Huang Yuenian2
1Nanjing Architectural and Civil Engineering Institute, Nanjing 210009, China
2Jinling Petrochemical Design Institute, Nanjing 210042, China
Keywords:
connectivity independent set Hamilton graph
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.

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