Forbidden subgraphs for hamiltonicity of 1-tough graphs
Hajo J. Broersma, Binlong Li, Shenggui Zhang · Discussiones Mathematicae Graph Theory · 2016
A graph G is said to be 1-tough if for every vertex cut S of G, the number of components of G -S does not exceed |S|. Being 1-tough is an obvious necessary condition for a graph to be hamiltonian, but it is not sufficient in general. We study the problem of characterizing all graphs H such that every 1-tough H-free graph is hamiltonian. We almost obtain a complete solution to this problem, leaving H = K 1 P 4 as the only open case.