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 wi...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 graph G has the hourglass property if every induced hourglass S（a tree with a degree sequence 22224） contains two non-adjacent vertices which have a common neighbor in G-V（S）.For an integer k≥4,a graph G has th...A graph G has the hourglass property if every induced hourglass S（a tree with a degree sequence 22224） contains two non-adjacent vertices which have a common neighbor in G-V（S）.For an integer k≥4,a graph G has the single k-cycle property if every edge of G,which does not lie in a triangle,lies in a cycle C of order at most k such that C has at least「｜V（C） /2」 edges which do not lie in a triangle,and they are not adjacent.In this paper,we show that every hourglass-free claw-free graph G of δ（G） ≥3 with the single 7-cycle property is Hamiltonian and is best possible;we also show that every claw-free graph G of δ（G） ≥3 with the hourglass property and with single 6-cycle property is Hamiltonian.展开更多
We prove the following result: Let G be a 2 connected claw free graph of order n(n≥3) and connectivity k . If for any independent set S k+1 with cardinality k+1 , there exist u,v∈S k+1 ...We prove the following result: Let G be a 2 connected claw free graph of order n(n≥3) and connectivity k . If for any independent set S k+1 with cardinality k+1 , there exist u,v∈S k+1 , such that |N(u)∩N(v)|≥(n-2k)/4 ,then G is Hamiltonian.展开更多
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 subgra...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.展开更多
In this paper we consider a property of claw-free graphs.We show that if d(u)+ d(v)≥ν(G)+2k+3,for every two nonadjacent vertices u and v,then G is 2k-vertex-deletable IM-extendable,whereν(G)=|V(G)|.And the bound is...In this paper we consider a property of claw-free graphs.We show that if d(u)+ d(v)≥ν(G)+2k+3,for every two nonadjacent vertices u and v,then G is 2k-vertex-deletable IM-extendable,whereν(G)=|V(G)|.And the bound is tight.展开更多
文摘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 }.
基金Supported by the National Natural Science Foundation of China(11071016 and 11171129)the Beijing Natural Science Foundation(1102015)
文摘A graph G has the hourglass property if every induced hourglass S（a tree with a degree sequence 22224） contains two non-adjacent vertices which have a common neighbor in G-V（S）.For an integer k≥4,a graph G has the single k-cycle property if every edge of G,which does not lie in a triangle,lies in a cycle C of order at most k such that C has at least「｜V（C） /2」 edges which do not lie in a triangle,and they are not adjacent.In this paper,we show that every hourglass-free claw-free graph G of δ（G） ≥3 with the single 7-cycle property is Hamiltonian and is best possible;we also show that every claw-free graph G of δ（G） ≥3 with the hourglass property and with single 6-cycle property is Hamiltonian.
文摘We prove the following result: Let G be a 2 connected claw free graph of order n(n≥3) and connectivity k . If for any independent set S k+1 with cardinality k+1 , there exist u,v∈S k+1 , such that |N(u)∩N(v)|≥(n-2k)/4 ,then G is Hamiltonian.
文摘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.
基金Supported by the National Natural Sciences Youth Foundation(10901144)
文摘In this paper we consider a property of claw-free graphs.We show that if d(u)+ d(v)≥ν(G)+2k+3,for every two nonadjacent vertices u and v,then G is 2k-vertex-deletable IM-extendable,whereν(G)=|V(G)|.And the bound is tight.
