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 = K1 ∪ P4 as the only open case.
@article{bwmeta1.element.doi-10_7151_dmgt_1897,
author = {Binlong Li and Hajo J. Broersma and Shenggui Zhang},
title = {Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {915-929},
zbl = {1350.05088},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1897}
}
Binlong Li; Hajo J. Broersma; Shenggui Zhang. Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 915-929. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1897/