| Let G be a graph on n vertices. We say G is hamiltonian if it contains a cycle of length n, and pancyclic if it contains a cycle of each possible length, from 3 up to n.; In this paper, we consider the property of (k, m)-pancyclicity, defined in 2004 by Faudree, Gould, Jacobson, and Lesniak. Given integers k and m with k ≤ m ≤ n, we say G is (k, m)- pancyclic if for any set S of k vertices in G and any integer r with m ≤ r ≤ n, there exists a cycle of length r in G which contains S. This property generalizes vertex pancyclicity, which requires any given vertex of G to be contained in cycles of each possible length, from 3 up to n.; Given a graph H, we say G is H-free if G does not contain H as an induced subgraph. In this context, we call H a forbidden subgraph. If F is a family of graphs, we say G is F -free if G is H-free for each H ∈ F . Faudree and Gould characterized the pairs of forbidden subgraphs which guarantee that a 2-connected graph of order n ≥ 10 is hamiltonian. There are ten such forbidden pairs, and the claw, K1,3, is a member of each.; For each of these ten pairs {lcub}R, S{rcub}, we find the smallest integer m such that any 2-connected {lcub}R, S{rcub}-free graph is guaranteed to be (k, m)-pancyclic. We then provide an example which shows that the achieved value m is best (smallest) possible under the given conditions. Each such example we utilize represents an infinite family of graphs.; Let sigma2(G) = min{lcub}d( x) + d(y) : xy ∉ E(G){rcub}. We also show that if G is claw-free and sigma2(G) ≥ n, then G is (k, 2k)-pancyclic for each k ≥ 2. The bound on sigma2( G) is sharp. |
