Tian Feng
Journal of Systems Science and Complexity. 1991, 4(4): 374-382.
Combining forbidden subgraphs with degree restrictions and neighborhood union restrictions, 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 subgraph L 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 the circumference of G is at least c, where V_1(L) is the set of vertices with degree 1 of L, S_c is the 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 subgraph L of G isomorphic to K_(1,3) or P_4, d_L(u,v)=2 \Rightarrow |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.