Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs

Binlong Li, Hajo J. Broersma, and Shenggui Zhang. "Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs." Discussiones Mathematicae Graph Theory 36.4 (2016): 915-929. <http://eudml.org/doc/287118>.

@article{BinlongLi2016,
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.},
author = {Binlong Li, Hajo J. Broersma, Shenggui Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {forbidden subgraph; 1-tough graph; H-free graph; hamiltonian graph; -free graph; Hamiltonian graph},
language = {eng},
number = {4},
pages = {915-929},
title = {Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs},
url = {http://eudml.org/doc/287118},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Binlong Li
AU - Hajo J. Broersma
AU - Shenggui Zhang
TI - Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 4
SP - 915
EP - 929
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 = K1 ∪ P4 as the only open case.
LA - eng
KW - forbidden subgraph; 1-tough graph; H-free graph; hamiltonian graph; -free graph; Hamiltonian graph
UR - http://eudml.org/doc/287118
ER -