Contents

Forbidden Subgraphs and Cycle Extendability

Ralph Faudree1, Zden&ék Ryjééek2, Ingo Schiermeyer3
1 Department of Mathernatical Sciences Memphis State University Memphis, TN 38152 U.S.A.
2Department of Mathematics University of West Bohemia 30614 Pilsen Czech Republic
3Lehrstuhl C fiir Mathematik Technische Hochschule Aachen D-52056 Aachen Germany

Abstract

A graph \(G\) on \(n\) vertices is \({pancyclic}\) if \(G\) contains cycles of all lengths \(\ell\) for \(3 \leq \ell \leq n\) and \(G\) is \({cycle \; extendable}\) if for every non-hamiltonian cycle \(C \subset G\) there is a cycle \(C’ \subset G\) such that \(V(C) \subset V(C’)\) and \(|V(C’) \setminus V(C)| = 1\). We prove that

  1. every \(2\)-connected \(K_{1,3}\)-free graph is pancyclic, if \(G\) is \(P_5\)-free and \(n \geq 6\), if \(G\) is \(P_6\)-free and \(n \geq 10\), or if \(G\) is \(P_7\)-free, deer-free and \(n \geq 14\), and
  2. every \(2\)-connected \(K_{1,3}\)-free and \(Z_2\)-free graph on \(n \geq 10\) vertices is cycle extendible using at most two chords of the cycle.