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
}
Forbidden subgraphs for hamiltonicity of 1-tough graphs. / Broersma, Haitze J.; Li, Binlong; Zhang, Shenggui.
In: Discussiones mathematicae. Graph theory, Vol. 36, No. 4, 10.2016, p. 915-929.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 -