Let a,b,k,r be nonnegative integers with 1 ≤ a ≤b and r ≥ 2. Let G be a graph of order n with n 〉 （a＋b）（r（a＋b）-2）＋ak/a. In this paper, we first show a characterization for all fractional （a, b, k）-criti...Let a,b,k,r be nonnegative integers with 1 ≤ a ≤b and r ≥ 2. Let G be a graph of order n with n 〉 （a＋b）（r（a＋b）-2）＋ak/a. In this paper, we first show a characterization for all fractional （a, b, k）-critical graphs. Then using the result, we prove that G is all fractional （a, b, k）-critical if δ（G） ≥ （r-1）b2/a ＋k and ｜NG（xl） ∪NG（x2） ∪... ∪NG（xr）｜ ≥ bn＋ak/a＋b for any independent subset {xl, x2, .., xr} in G. Furthermore, it is shown that the lower bound on the condition ｜NG（xl） ∪NG（x2） ∪... ∪NG（xr）｜ ≥ bn=ak/ a＋b is best possible in some sense, and it is an extension of Lu＇s previous result.展开更多
Let G be a connected graph of order n, and NC2(G) denote min{|N(u)U(v) |:dist(u,v) = 2}, where dist(u,v) is the distance between u and v in G. A cycle C in Gis called a dominatiny cycle, if V(G)\V(C) is an independent...Let G be a connected graph of order n, and NC2(G) denote min{|N(u)U(v) |:dist(u,v) = 2}, where dist(u,v) is the distance between u and v in G. A cycle C in Gis called a dominatiny cycle, if V(G)\V(C) is an independent set in G. In this paper, weprove that if G contains a domillating cycle and 2, then G contains a dominating cycleof length at least min{n, 2NC2(G) - 2}, which proves partially a conjecture of R. Shenand F. Tian. And we give a class of graphs that show the result is shrpg.展开更多
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 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.展开更多
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.展开更多
基金Supported by National Natural Science Foundation of China(Grant No.11371009)
文摘Let a,b,k,r be nonnegative integers with 1 ≤ a ≤b and r ≥ 2. Let G be a graph of order n with n 〉 （a＋b）（r（a＋b）-2）＋ak/a. In this paper, we first show a characterization for all fractional （a, b, k）-critical graphs. Then using the result, we prove that G is all fractional （a, b, k）-critical if δ（G） ≥ （r-1）b2/a ＋k and ｜NG（xl） ∪NG（x2） ∪... ∪NG（xr）｜ ≥ bn＋ak/a＋b for any independent subset {xl, x2, .., xr} in G. Furthermore, it is shown that the lower bound on the condition ｜NG（xl） ∪NG（x2） ∪... ∪NG（xr）｜ ≥ bn=ak/ a＋b is best possible in some sense, and it is an extension of Lu＇s previous result.
文摘Let G be a connected graph of order n, and NC2(G) denote min{|N(u)U(v) |:dist(u,v) = 2}, where dist(u,v) is the distance between u and v in G. A cycle C in Gis called a dominatiny cycle, if V(G)\V(C) is an independent set in G. In this paper, weprove that if G contains a domillating cycle and 2, then G contains a dominating cycleof length at least min{n, 2NC2(G) - 2}, which proves partially a conjecture of R. Shenand F. Tian. And we give a class of graphs that show the result is shrpg.
基金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.
文摘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.
文摘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.
