摘要
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.
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_1(L)∩S_c|≥2 if L≌K_(1,3),and |V(L)∩S_c|≥1 if L≌P_4,then thecircumference of G is at least c,where V_1(L)is the set of vertices with degree 1 of L,S_c isthe set of vertices with degree at least c/2 of G and P_4 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_(1,3)or P_4,d_L(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.
基金
A work supported by National Natural Science Foundation of China
