Forbidden subgraphs for hamiltonicity of 1-tough graphs

Binlong Li; Hajo J. Broersma; Shenggui Zhang

doi:10.7151/dmgt.1897

Forbidden subgraphs for hamiltonicity of 1-tough graphs

Binlong Li, Hajo J. Broersma, Shenggui Zhang

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

3 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	English
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
1-tough
Toughness

Access to Document

10.7151/dmgt.1897

Fingerprint Dive into the research topics of 'Forbidden subgraphs for hamiltonicity of 1-tough graphs'. Together they form a unique fingerprint.

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, 1-tough, Toughness",

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

year = "2016",

month = oct,

doi = "10.7151/dmgt.1897",

language = "English",

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 - Li, Binlong

AU - Broersma, Hajo J.

AU - Zhang, Shenggui

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 - 1-tough

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 -