WU Zhengsheng;XU Xinping;ZHOU Xinghe
Journal of Systems Science and Complexity. 1998, 11(3): 230-237.
Let G be a graph. An independent set Y in G is called an essential independent set (or essential set for simplicity) if there is {y_1 , y_2} Y such that dist(y_1 , y_2) = 2. For integer t > 0, let I_t(G) = {Y| Y is an independent set of G, |Y| = t}, I^*_t(G) = {Y|Y is an essential set of G, |Y| = t}. For Y∈I_t (G), let s_i(y) = |{v|v ∈V(G), |N(v) n Y| = i}|(i = 0, 1,…, t). Let X, Y ∈ V(G). Define dist(X, Y) =\min_{u∈ X,v∈Y}dist(u, v), n(Y) = |{v|v ∈V(G), dist({v}, Y) ≤ 2}|. A non-negative rational sequence (a1，a2,…, ak+1) (k ≥2) is called an LTW-sequence, if it satisfies 1) a1 ≤ 1; 2) for arbitrary i1, i2,…，ih. ∈{2,3,……, k + 1}, \sum_{j+1}^h i_j\leq k+1 implies \sum_{j=1}^h (a_{i_j}-1)\leq 1. The main new results of this paper are as follows: Let (a1， a2，… a_{k+1}) be all LTW-sequence, and k ≥ 2. If G is a k-connected graph, and \sum_{i=1}^{k+1}a_i s_i (Y)> n(Y)-1 for each Y∈I^*_{k+1}(G), then G has a Hamilton cycle; if G is a (k + 1)-connected graph and \sum_{i=1}^{k+1}a_i s_i (Y)> n(Y) for each Y∈I^*_{k+1}(G), then G is Hamilton-connected. The existing results are generalized by these since I_{k+1}(G) is replaced by I^*_{k+1}(G). We introduce a new technique of T-insertion in this paper， by using the T-vertex inserting lemmas we give a unified proof for a graph to be hamiltonian or Hamilton-connected.
