Restrictions on Induced Subgraphs Ensuring Hamiltonicity or Pancyclicity of K sub 1,3-Free Graphs

摘要

The Goodman and Hedetniemi (1974) result that every 2-connected graph containing no induced subgraph isomorphic to K sub 1, 3 or K sub 1, 3 +e is Hamiltonian is improved by showing that a graph G is pancyclic if G contains no induced K sub 1,3 while in every induced subgraph H isomorphic to K sub 1,3 +e certain pairs of vertices have a common neighbor outside H. It is shown that other sufficient conditions for Hamiltonicity or pancyclicity in terms of forbidden induced subgraphs can be relaxed in a similar way. Results of Gould and Jacobson (1982) are generalized.