Forbidden subgraphs for hamiltonicity of 1-tough graphs

Haitze J. Broersma; Binlong Li; Shenggui Zhang

doi:10.7151/dmgt.1897

Forbidden subgraphs for hamiltonicity of 1-tough graphs

Haitze J. Broersma, Binlong Li, Shenggui Zhang

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

2 Citations (Scopus)

15 Downloads (Pure)

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 = K_1 ∪ P_4 as the only open case.

Original language	Undefined
Pages (from-to)	915-929
Number of pages	15
Journal	Discussiones mathematicae. Graph theory
Volume	36
Issue number	4
DOIs	https://doi.org/10.7151/dmgt.1897
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

Access to Document

10.7151/dmgt.1897

http://dx.doi.org/10.7151/dmgt.1897

Cite this

@article{ac5d1ae80fbc48f1966afe53f1692926,

title = "Forbidden subgraphs for hamiltonicity of 1-tough graphs",

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 = K_1 ∪ P_4 as the only open case.",

keywords = "MSC-05C07, Hamiltonian graph, MSC-05C45, MSC-05C38, H-free graph, Forbidden subgraph, IR-101997, 1-tough, METIS-319456, EWI-27290, Toughness",

author = "Broersma, {Haitze J.} and Binlong Li and Shenggui Zhang",

note = "10.7151/dmgt.1897",

year = "2016",

month = "10",

doi = "10.7151/dmgt.1897",

language = "Undefined",

volume = "36",

pages = "915--929",

journal = "Discussiones mathematicae. Graph theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

number = "4",

}

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 -