### Abstract

Original language | Undefined |
---|---|

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
- IR-101997
- 1-tough
- METIS-319456
- EWI-27290
- Toughness

### Cite this

*Discussiones mathematicae. Graph theory*,

*36*(4), 915-929. https://doi.org/10.7151/dmgt.1897

}

*Discussiones mathematicae. Graph theory*, vol. 36, no. 4, pp. 915-929. https://doi.org/10.7151/dmgt.1897

**Forbidden subgraphs for hamiltonicity of 1-tough graphs.** / Broersma, Haitze J.; Li, Binlong; Zhang, Shenggui.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - Forbidden subgraphs for hamiltonicity of 1-tough graphs

AU - Broersma, Haitze J.

AU - Li, Binlong

AU - Zhang, Shenggui

N1 - 10.7151/dmgt.1897

PY - 2016/10

Y1 - 2016/10

N2 - 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.

AB - 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.

KW - MSC-05C07

KW - Hamiltonian graph

KW - MSC-05C45

KW - MSC-05C38

KW - H-free graph

KW - Forbidden subgraph

KW - IR-101997

KW - 1-tough

KW - METIS-319456

KW - EWI-27290

KW - Toughness

U2 - 10.7151/dmgt.1897

DO - 10.7151/dmgt.1897

M3 - Article

VL - 36

SP - 915

EP - 929

JO - Discussiones mathematicae. Graph theory

JF - Discussiones mathematicae. Graph theory

SN - 1234-3099

IS - 4

ER -