We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
FORBIDDEN SUBGRAPHS FOR HAMILTONICITY OF 1-TOUGH GRAPHS.
- Authors
BINLONG LI; BROERSMA, HAJO J.; SHENGGUI ZHANG
- 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 = K1 [ P4 as the only open case.
- Subjects
SUBGRAPHS; HAMILTONIAN graph theory; PROBLEM solving; NUMBER theory; MATHEMATICAL analysis
- Publication
Discussiones Mathematicae: Graph Theory, 2016, Vol 36, Issue 4, p915
- ISSN
1234-3099
- Publication type
Article
- DOI
10.7151/dmgt.1897