Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 915-929 |
Number of pages | 15 |
Journal | Discussiones mathematicae. Graph theory |
Volume | 36 |
Issue number | 4 |
DOIs | |
Publication status | Published - Oct 2016 |
Keywords
- MSC-05C07
- Hamiltonian graph
- MSC-05C45
- MSC-05C38
- H-free graph
- Forbidden subgraph
- 1-tough
- Toughness
- 2023 OA procedure