Hamiltonicity,neighborhood union and square graphs of claw-free graphs

Let G be a graph, the square graph G 2 of G is a graph satisfying V(G 2)=V(G) and E(G 2)=E(G)∪｛uv: dist G(u, v)=2｝ . In this paper, we use the technique of vertex insertion on l -connected ( l=k or k+1, k≥2 ) claw-free graphs to provide a unified proof for G to be Hamiltonian, 1 -Hamiltonian or Hamiltonian-connected. The sufficient conditions are expressed by the inequality concerning ∑ k i=0N(Y i) and n(Y) in G for each independent set Y=｛y 0, y 1, …, y k｝ of the square graph of G , where b ( 0<b<k+1 ) is an integer, Y i=｛y i, y i-1, …, y i-(b-1)｝Y for i∈｛0, 1, …, k｝ , where subscriptions of y j s will be taken modulo k+1 , and n(Y)=｛v∈ V(G): dist (v, Y)≤ 2｝ .

Neighborhood Union of Essential Sets and Hamiltonicity of Claw-Free Graphs

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. In this paper, we will use the technique of the vertex insertion on l connected ( l=k or k+1,k≥2 ) claw free graphs to provide a unified proof for G to be hamiltonian or 1 hamiltonian, the sufficient conditions are expressed by the inequality concerning ∑ki=0N(Y i) and n(Y) for each essential set Y={y 0,y 1,...,y k} of G , where Y i={y i,y i-1 ,...,y i-(b-1) }Y for i∈{0,1,...,k} (the subscriptions of y j ’s will be taken modulo k+1 ), b ( 0【b【k+1 ) is an integer, and n(Y)={v∈V(G): dist (v,Y)≤2 }.

A Sufficient Condition for 2-Distance-Dominating Cycles

A cycle C of a graph G is a m-distance-dominating cycle if for all vertices of . Defining denotes the minimum value of the degree sum of any k independent vertices of G. In this paper, we prove that if G is a 3-connected graph on n vertices, and if , then every longest cycle is m-distance-dominating cycles.

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 UV(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.

Spanning 3-ended trees in k-connected K_(1,4)-free graphs

A tree with at most m leaves is called an m-ended tree.Kyaw proved that every connected K1,4-free graph withσ4(G)n-1 contains a spanning 3-ended tree.In this paper we obtain a result for k-connected K1,4-free graphs with k 2.Let G be a k-connected K1,4-free graph of order n with k 2.Ifσk+3(G)n+2k-2,then G contains a spanning 3-ended tree.

Hamiltonicity of 4-connected Graphs

Let σk（G） denote the minimum degree sum of k independent vertices in G and α（G） denote the number of the vertices of a maximum independent set of G. In this paper we prove that if G is a 4-connected graph of order n and σ5（G） 〉 n ＋ 3σ（G） ＋ 11, then G is Hamiltonian.

A New Neighborhood Union Condition for Hamiltonian Graphs

For a vertex set{u1,u2,…,uk}of a graph G with n vertices,let s（G;{u1,u2,…,uk}）=Σ1≤i≤j≤k|N（ui）UN（uj）|, NCk.=min{s（G;{x1,…,xk}）:{x1,…,xk}is an independent set}. In this paper,we shall prove that if G is 3-connected and NC4≥3n,then G is either a hamiltonian or Petersen graph.This generalizes some results on the neighborhood union conditions for hamiltonian graphs.

Generalization of Ore's Theorem

Let G be a graph. The partially square graph G~* of G is a graph obtainedfrom G by adding edges uv satisfying the conditions uv E(G), and there is somew ∈N(u)∩N(v), such that N(w) N(u:)∪ N(v)∪ {u, v}. In this paper, we will use thetechnique of the vertex insertion on l-connected (l=k or k+1, k≥2) graphs to providea unified proof for G to be hamiltonian , 1-hamiltonian or hamiltonia11-connected. Thesufficient conditions are expresscd by the inequality concerning sum from i=1 to k |N(Y_i)| and n(Y) in Gfor each independent set Y={y_1, y_2,…,y_k} in G~*, where K_i= {y_i, y_(i-1),…,y_(i-(b-1)) }Y for i ∈{1, 2,…,k} (the subscriptions of y_j's will be taken modulo k), 6 (0 <b <k)is an integer,and n(Y) = |{v∈V(G): dist(v,Y) ≤2}|.