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 }.展开更多
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.展开更多
Let G be a graph of order n and X V(G). G is called X-cyclable if G has an X-cycle, i.e., a cycle containing all vertices of X. Define the parameters a(X) = max{|S| S is an independent vertex set in G[X] induced by X...Let G be a graph of order n and X V(G). G is called X-cyclable if G has an X-cycle, i.e., a cycle containing all vertices of X. Define the parameters a(X) = max{|S| S is an independent vertex set in G[X] induced by X}, σk(X) = min{∑ki=1dG(x.i| {x1, x1…, xk} is an independent vertex set in G[X]} and NCk(X) = min{|∪ki=1 NG(xi)| | {x1, x2…,xk} is an independent vertex set in G[X] }. Our main result is as follows: If G is a 1-tough graph and X V(G) with σ3(X)≥ n, then for every integer t ≥ 1, G has a cycle C containing at least min{|X|, (2|X| - n + 3δ + 1 - t), |X| + NCt(X) - a(X)} venices of X, where δ(X) = [σ3(X)]. This result further extends previous results in H.J. Broersma et al. in terms of X-cyclability. We also obtain that if G is a 1-tough graph with σ3 (X) ≥ n, then for every integer t ≥ 1, G has a cycle containing at least min{|X|, (4|X|- 2n+4δ(X) + 1 - 2t), NCt (X) +NCt (X)} vertices of X, where NCt (X) = min{|N(I) ∩X|| I is an independent set of t vertices of X}. Analogous results are established for 2-connected graphs.展开更多
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.展开更多
M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + ...M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + 2, n} or G belongs to one exceptional class of graphs.展开更多
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.展开更多
Let C be a 2-connected graph on > 2 31 venices. G is called pancyclic if itcontains a cycle of length I for every I such that 3 l n. In this paper we shall prove thatif IN(u) U N(v) Z (2n - 3)/3 for any nonadjacent...Let C be a 2-connected graph on > 2 31 venices. G is called pancyclic if itcontains a cycle of length I for every I such that 3 l n. In this paper we shall prove thatif IN(u) U N(v) Z (2n - 3)/3 for any nonadjacent pair uv E V(G), then G is pancyclic.展开更多
A graph G is claw\|free if G has no induced subgraph isomorphic to K\-\{1,3\}. And a graph G is pancyclic if for every m, 3≤m≤|V(G)|, there is a cycle of length m. This paper considered neighbourhood union for any p...A graph G is claw\|free if G has no induced subgraph isomorphic to K\-\{1,3\}. And a graph G is pancyclic if for every m, 3≤m≤|V(G)|, there is a cycle of length m. This paper considered neighbourhood union for any pair of nonadjacent vertices in claw\|free graph and obtained the following theorem: If G is a 2\|connected claw\|free graph of order n≥12 and |N(u)∪N(v)|+|N(u)∪N(w)|+|N(v)∪N(w)|≥2n-1 for any three pairwise nonadjacent vertices u,v, and w, then G is pancyclic.展开更多
文摘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 }.
文摘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.
基金the Natural Science Foundation of Yunnan Province.
文摘Let G be a graph of order n and X V(G). G is called X-cyclable if G has an X-cycle, i.e., a cycle containing all vertices of X. Define the parameters a(X) = max{|S| S is an independent vertex set in G[X] induced by X}, σk(X) = min{∑ki=1dG(x.i| {x1, x1…, xk} is an independent vertex set in G[X]} and NCk(X) = min{|∪ki=1 NG(xi)| | {x1, x2…,xk} is an independent vertex set in G[X] }. Our main result is as follows: If G is a 1-tough graph and X V(G) with σ3(X)≥ n, then for every integer t ≥ 1, G has a cycle C containing at least min{|X|, (2|X| - n + 3δ + 1 - t), |X| + NCt(X) - a(X)} venices of X, where δ(X) = [σ3(X)]. This result further extends previous results in H.J. Broersma et al. in terms of X-cyclability. We also obtain that if G is a 1-tough graph with σ3 (X) ≥ n, then for every integer t ≥ 1, G has a cycle containing at least min{|X|, (4|X|- 2n+4δ(X) + 1 - 2t), NCt (X) +NCt (X)} vertices of X, where NCt (X) = min{|N(I) ∩X|| I is an independent set of t vertices of X}. Analogous results are established for 2-connected graphs.
文摘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.
文摘M. Matthews and D. Sumner proved that if G is a 2-connected claw-free graph of order n, then c(G) min{2δb + 4, n}. In this paper, we prove that if G is a,2-connected claw-free graph on n venices, then c(G) min{3δ + 2, n} or G belongs to one exceptional class of graphs.
基金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.
文摘Let C be a 2-connected graph on > 2 31 venices. G is called pancyclic if itcontains a cycle of length I for every I such that 3 l n. In this paper we shall prove thatif IN(u) U N(v) Z (2n - 3)/3 for any nonadjacent pair uv E V(G), then G is pancyclic.
基金Supported by the National Natural Science Foundationof China(No.196 710 5 0 )
文摘A graph G is claw\|free if G has no induced subgraph isomorphic to K\-\{1,3\}. And a graph G is pancyclic if for every m, 3≤m≤|V(G)|, there is a cycle of length m. This paper considered neighbourhood union for any pair of nonadjacent vertices in claw\|free graph and obtained the following theorem: If G is a 2\|connected claw\|free graph of order n≥12 and |N(u)∪N(v)|+|N(u)∪N(w)|+|N(v)∪N(w)|≥2n-1 for any three pairwise nonadjacent vertices u,v, and w, then G is pancyclic.
