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

School of Mathematics and Statistics

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

9 Scopus citations

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₁ ∪ P₄ 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
State	Published - 2016

Keywords

1-tough graph
Forbidden subgraph
H-free graph
Hamiltonian graph

Access to Document

10.7151/dmgt.1897

Cite this

@article{87ca975da51c4fcdbf991b9187b0bd48,

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

keywords = "1-tough graph, Forbidden subgraph, H-free graph, Hamiltonian graph",

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

year = "2016",

doi = "10.7151/dmgt.1897",

language = "英语",

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

Y1 - 2016

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

KW - 1-tough graph

KW - Forbidden subgraph

KW - H-free graph

KW - Hamiltonian graph

UR - http://www.scopus.com/inward/record.url?scp=84994236066&partnerID=8YFLogxK

U2 - 10.7151/dmgt.1897

DO - 10.7151/dmgt.1897

M3 - 文章

AN - SCOPUS:84994236066

SN - 1234-3099

VL - 36

SP - 915

EP - 929

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

IS - 4

ER -

Forbidden subgraphs for hamiltonicity of 1-tough graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this