[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 Xiaoyue^1*;  Huang Yuenian²

¹Nanjing Architectural and Civil Engineering Institute, Nanjing 210009, China
²Jinling 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.

Common functions