NEIGHBORHOOD UNION OF INDEPENDENT SETS AND HAMILTONICITY OF CLAW-FREE GRAPHS

Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u. For any U V(G) ,let N(U)=Uu,∈UN(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K1.3. One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al. : Let G be a 2-connected claw-free graph of order n,and d(u) d(v) d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that, for any three positive integers s ,t and w,such that if G is a (s t w-1)connected claw-free graph of order n,and d(S) d(T) d(W)＞n-(s t w) for every three disjoint independent vertex sets S,T,W with |S |=s, |T|=t, |W|=w,and S∪T∪W is also independent ,then G is Hamiltonian. Other related results are obtained too.

Neighborhood union of independent sets and hamiltonicity of claw-free graphs

Let G be a graph, for any u∈V(G), let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u. For any U⊆V(G), let N(U)=∪ _u εU N(u), and d(U)=|N(U)|. A graph G is called claw-free if it has no induced subgraph isomorphic to K _1,3. One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng, et al.: Let G be a 2-connected claw-free graph of order n, and d(u)+d(v)+d(w)≥n−2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that, for any three positive integers s,t and w, such that if G is a (s+t+w−1)-connected claw-free graph of order n, and d(S)+d(T)+d(W)>n−(s+t+w) for every three disjoint independent vertex sets S,T,W with |S|=s, |T|=t, |W|=w, and S∪T∪W is also independent, then G is Hamiltonian. Other related results are obtained too. Supported by the National Natural Science Foundation of China(10371055,10471037).