Opuscula Math. 37, no. 4 (), 617-639
http://dx.doi.org/10.7494/OpMath.2017.37.4.617
Opuscula Mathematica

# Fan's condition on induced subgraphs for circumference and pancyclicity

Abstract. Let $$\mathcal{H}$$ be a family of simple graphs and $$k$$ be a positive integer. We say that a graph $$G$$ of order $$n\geq 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: $\forall u,v\in 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 $$G\in\mathcal{F}(\mathcal{H},k)$$. In this paper we show that if $$G$$ is $$2$$-connected and $$G\in\mathcal{F}(\{K_{1,3},P_4\},k)$$, then $$G$$ contains a cycle of length at least $$k$$, and that if $$G\in\mathcal{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.
Keywords: Fan's condition, circumference, hamiltonian cycle, pancyclicity.
Mathematics Subject Classification: 05C38, 05C45.