Fan's condition on induced subgraphs for circumference and pancyclicity

摘要

Let (mathcal{H}) be a family of simple graphs and (k) be a positive integer. We say that a graph (G) of order (ngeq k) satisfies Fan's condition with respect to (mathcal{H}) with constant (k), if for every induced subgraph (H) of (G) isomorphic to any of the graphs from (mathcal{H}) the following holds: [orall u,vin V(H)colon d_H(u,v)=2,Rightarrow max{d_G(u),d_G(v)}geq k/2.] If (G) satisfies the above condition, we write (Ginmathcal{F}(mathcal{H},k)). In this paper we show that if (G) is (2)-connected and (Ginmathcal{F}({K_{1,3},P_4},k)), then (G) contains a cycle of length at least (k), and that if (Ginmathcal{F}({K_{1,3},P_4},n)), then (G) is pancyclic with some exceptions. As corollaries we obtain the previous results by Fan, Benhocine and Wojda, and Ning.