×

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
PDF BibTeX XML Cite