# Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs

Binlong Li; Hajo J. Broersma; Shenggui Zhang

Discussiones Mathematicae Graph Theory (2016)

- Volume: 36, Issue: 4, page 915-929
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topBinlong 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 -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.