# zbMATH — the first resource for mathematics

Forbidden subgraphs and cycle extendability. (English) Zbl 0839.05059
The authors present some sufficient conditions for hamiltonicity of 2-connected graphs in terms of forbidden induced subgraphs. These conditions even ensure stronger properties than hamiltonicity: A graph $$G$$ on $$n$$ vertices is called pancyclic if $$G$$ contains a cycle of length $$\ell$$ for each $$\ell$$ between 3 and $$n$$. $$G$$ is called cycle extendable if for each nonhamiltonian cycle $$C$$ in $$G$$, there is a cycle $$C'$$ in $$G$$ with $$V(C)\subseteq V(C')$$ and $$|V(C')\backslash V(C)|= 1$$. It is proved that every sufficiently large 2-connected graph is (i) pancyclic if it does not contain an induced subgraph that is a claw (i.e. isomorphic to $$K_{1,3}$$), a path on 7 vertices, or a deer (i.e. a path $$v_1 v_2\cdots v_7$$ extended by the chord $$v_3 v_5$$), and (ii) cycle extendable if it does not contain an induced subgraph that is a claw or a path $$v_1 v_2 v_3 v_4 v_5$$ extended by the chord $$v_1 v_3$$.
Reviewer: A.Huck

##### MSC:
 05C38 Paths and cycles 05C45 Eulerian and Hamiltonian graphs