Forbidden subgraphs and cycle extendability. (English) Zbl 0839.05059

Faudree, Ralph; Ryjáček, Zdeněk; Schiermeyer, Ingo

J. Comb. Math. Comb. Comput. 19, 109-128 (1995).

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

Keywords:

cycle extendability; hamiltonicity; pancyclic; cycle extendable; 2-connected graph