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.展开更多
For a vertex set{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>}of a graph G with n vertices,let s（G;{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>...For a vertex set{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>}of a graph G with n vertices,let s（G;{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>}）=Σ<sub>1</sub>≤i≤j≤k<sup>|N（u<sub>i</sub>）UN（u<sub>j</sub>）|</sup>, NC<sub>k</sub>.=min{s（G;{x<sub>1</sub>,…,x<sub>k</sub>}）:{x<sub>1</sub>,…,x<sub>k</sub>}is an independent set}. In this paper,we shall prove that if G is 3-connected and NC<sub>4</sub>≥3n,then G is either a hamiltonian or Petersen graph.This generalizes some results on the neighborhood union conditions for hamiltonian graphs.展开更多
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.展开更多
Combining forbidden subgraphs with degree restrictions and neighborhood unionrestrictions,respectively,we prove the following results:（1） Let G be a 2-connected graph of order n,and 3≤c≤n.If for each induced subgr...Combining forbidden subgraphs with degree restrictions and neighborhood unionrestrictions,respectively,we prove the following results:（1） Let G be a 2-connected graph of order n,and 3≤c≤n.If for each induced subgraphL of order four of G（?）|V<sub>1</sub>（L）∩S<sub>c</sub>|≥2 if L≌K<sub>1,3</sub>,and |V（L）∩S<sub>c</sub>|≥1 if L≌P<sub>4</sub>,then thecircumference of G is at least c,where V<sub>1</sub>（L）is the set of vertices with degree 1 of L,S<sub>c</sub> isthe set of vertices with degree at least c/2 of G and P<sub>4</sub> is a path of order 4.（2） Let G be a 2-connected graph of order n,and n≥s+2.If for each induced subgraphL of G isomorphic to K<sub>1,3</sub>or P<sub>4</sub>,d<sub>L</sub>（u,v）=2（?）|N（u）∪N（v）|≥s,then the circumferencec （G） of G is at least s+2.Moreover,if n≥s+3 and s is odd,then c（G）≥s+3.展开更多
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.展开更多
文摘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 Science Foundation of ChinaSupported also by the Post-doctoral Foundation of China
文摘For a vertex set{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>}of a graph G with n vertices,let s（G;{u<sub>1</sub>,u<sub>2</sub>,…,u<sub>k</sub>}）=Σ<sub>1</sub>≤i≤j≤k<sup>|N（u<sub>i</sub>）UN（u<sub>j</sub>）|</sup>, NC<sub>k</sub>.=min{s（G;{x<sub>1</sub>,…,x<sub>k</sub>}）:{x<sub>1</sub>,…,x<sub>k</sub>}is an independent set}. In this paper,we shall prove that if G is 3-connected and NC<sub>4</sub>≥3n,then G is either a hamiltonian or Petersen graph.This generalizes some results on the neighborhood union conditions for hamiltonian graphs.
文摘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 work supported by National Natural Science Foundation of China
文摘Combining forbidden subgraphs with degree restrictions and neighborhood unionrestrictions,respectively,we prove the following results:（1） Let G be a 2-connected graph of order n,and 3≤c≤n.If for each induced subgraphL of order four of G（?）|V<sub>1</sub>（L）∩S<sub>c</sub>|≥2 if L≌K<sub>1,3</sub>,and |V（L）∩S<sub>c</sub>|≥1 if L≌P<sub>4</sub>,then thecircumference of G is at least c,where V<sub>1</sub>（L）is the set of vertices with degree 1 of L,S<sub>c</sub> isthe set of vertices with degree at least c/2 of G and P<sub>4</sub> is a path of order 4.（2） Let G be a 2-connected graph of order n,and n≥s+2.If for each induced subgraphL of G isomorphic to K<sub>1,3</sub>or P<sub>4</sub>,d<sub>L</sub>（u,v）=2（?）|N（u）∪N（v）|≥s,then the circumferencec （G） of G is at least s+2.Moreover,if n≥s+3 and s is odd,then c（G）≥s+3.
基金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.
