THE NEIGHBORHOOD INTERSECTIONS OF ESSENTIAL SETS AND HAMILTONICITY OFGRAPHS  

作　　者：WU Zhengsheng(Department of Mathematics, Naming Normal University, Naming 210097, China)XU Xinping(Department of Mathematics, Jiangsu Education College, Naming 210013, China)ZHOU Xinghe(Department of Mathematics, Naming Normal University, Nabbing 210097, 

出　　处：《Systems Science and Mathematical Sciences》1998年第3期230-237,共8页

摘　　要：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 {yi , y2} Y such that dist(y1 , y2) - 2. For integer t > 0, let It(G) = {Y| Y is an independent set of G, |Y| = t}, It(G) = {Y|Y is an essential set of G, |Y| = t}. For ∈E It(G), let si(y) = |{v|v ∈V(G), |N(v) n Y| = i}|(i = 0, 1,…, t). Let X, Y g V(G). Define dist(X, 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}, The main new results of this paper are as follows: Let (a1， a2，… ak+1) be all LTW-sequence, and k ≥ 2. If G is a k-connected graph, and then G has a Hamilton cycle; if G is a (k + 1)-connected graph and for each then G is Hamilton-connected. The existing results are generalized by these since Ik+1(G) is replaced by I(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.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 {yi , y2} Y such that dist(y1 , y2) - 2. For integer t > 0, let It(G) = {Y| Y is an independent set of G, |Y| = t}, It(G) = {Y|Y is an essential set of G, |Y| = t}. For ∈E It(G), let si(y) = |{v|v ∈V(G), |N(v) n Y| = i}|(i = 0, 1,…, t). Let X, Y g V(G). Define dist(X, 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}, The main new results of this paper are as follows: Let (a1， a2，… ak+1) be all LTW-sequence, and k ≥ 2. If G is a k-connected graph, and then G has a Hamilton cycle; if G is a (k + 1)-connected graph and for each then G is Hamilton-connected. The existing results are generalized by these since Ik+1(G) is replaced by I(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.

关 键 词：篖TW-sequence ESSENTIAL SETS T-vertex INSERTION HAMILTONICITY 

分 类 号：O157[理学—数学]