摘要
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.
源语言 | 英语 |
---|---|
页(从-至) | 915-929 |
页数 | 15 |
期刊 | Discussiones Mathematicae - Graph Theory |
卷 | 36 |
期 | 4 |
DOI | |
出版状态 | 已出版 - 2016 |