Several Sufficient Conditions On Hamiltonian Properties In Graphs

Let G be a graph. G is called traceable if G contains a Hamilton path. Let P be a path in G.If every component of G-V(P) has vertex number less than 2, then P is called a dominating path in G. G is called almost traceable if every longest path in G is dominating path.In this paper, by using the vertex inserting lemmas and the concept of LTW-sequences, we provide some new sufficient conditions for traceable and almost traceable graphs, which are related to the independent sets or the essential independent sets.Theorem 1 Let G be a (k ?l)-connected graph with k > 2, (01, 02, ???, ajt+i) bea Jfc-LTW-sequence. If a(Z] = ?aiSi(Z) > n(Z] - 1 for each Z e /^(G), then eitherG is trceable or G ?F, where F be the classes of graphs defined as follows: First take complete graphs Km1,,Km2,Km3(mi,m2,ms > 1) and K3,V(K3) = {b1,b2,b3}. Then let Kmi join 6i,i {1,2. 3}(i.e.bi adjacent to each vertex of Kmi).Corollary 1 Let G be a connected graph, if d(z1) + d(z2) + d(z3) - |N(za1) N(z2) N(z3)| > n(Z) - 2 for each Z = {z1,z2,z3) I3(e)(G), then either G is traceable orTheorem 2 Let G be a (k - l)-connected graph with k > 2, (a1,a2,.... ,ak+1) be ak-LTW-sequence. If > n(Z) + k-3 for each Z then G is almost traceable .Corollary 2 Let G be a connected graph, if d(z1) + d(z2) + d(z3) > n(Z) - 1 foreach Z = {z1,z2,z3) I3(e) (G), then G is almost traceable.We need the following denotes in Theroem 3 and Theorem 4. Letandwhere the subscription of each vertex in Yi is the same as the one in Y.Theorem 3 Let G be a (k - l)-connected graph with k > 2, b an integer, and , Ifin G for each Y Ik+1(G*), then G is almost traceable.Theorem 4 Let G be a (k-1)-connected graph with k > 2. b an integer, and 0 < b < k, b* = min{k,(2b-1+k)/2} Iffor each y (G), then G is almost traceable.In Theorem 5, let y = {y1,y2.... ,yk},Yi = {yi,yi-1,...... ,yi-(b-1)},i {1,2,.... , k}, where the subscription of each vertex in Yi is the same as the one in Y.Theorem 5 Let G be a (k - l)-connected with k > 2, b an integer, and 0 < b < kIf (Y) = Ei 1 |N(Yi)\ > (b-1+k)/2(n(Y) - 2) for each Y I(ke)(G), then G is traceable.