Forbidden subgraphs for hamiltonicity of 1-tough graphs

Haitze J. Broersma, Binlong Li, Shenggui Zhang

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 languageUndefined
Pages (from-to)915-929
Number of pages15
JournalDiscussiones mathematicae. Graph theory
Volume36
Issue number4
DOIs
StatePublished - 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

Cite this

Broersma, Haitze J.; Li, Binlong; Zhang, Shenggui / Forbidden subgraphs for hamiltonicity of 1-tough graphs.

In: Discussiones mathematicae. Graph theory, Vol. 36, No. 4, 10.2016, p. 915-929.

Research output: Scientific - peer-review › Article

@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",
volume = "36",
pages = "915--929",
journal = "Discussiones mathematicae. Graph theory",
issn = "1234-3099",
publisher = "University of Zielona Gora",
number = "4",

}

Broersma, HJ, Li, B & Zhang, S 2016, 'Forbidden subgraphs for hamiltonicity of 1-tough graphs' Discussiones mathematicae. Graph theory, vol 36, no. 4, pp. 915-929. DOI: 10.7151/dmgt.1897

Forbidden subgraphs for hamiltonicity of 1-tough graphs. / Broersma, Haitze J.; Li, Binlong; Zhang, Shenggui.

In: Discussiones mathematicae. Graph theory, Vol. 36, No. 4, 10.2016, p. 915-929.

Research output: Scientific - peer-review › Article

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

T2 - Discussiones mathematicae. Graph theory

JF - Discussiones mathematicae. Graph theory

SN - 1234-3099

IS - 4

ER -

Broersma HJ, Li B, Zhang S. Forbidden subgraphs for hamiltonicity of 1-tough graphs. Discussiones mathematicae. Graph theory. 2016 Oct;36(4):915-929. Available from, DOI: 10.7151/dmgt.1897

Access to Document