Forbidden subgraphs for hamiltonicity of 1-tough graphs

Binlong Li, Hajo J. Broersma, Shenggui Zhang

科研成果: 期刊稿件文章同行评审

9 引用 (Scopus)

摘要

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.

源语言英语
页(从-至)915-929
页数15
期刊Discussiones Mathematicae - Graph Theory
36
4
DOI
出版状态已出版 - 2016

指纹

探究 'Forbidden subgraphs for hamiltonicity of 1-tough graphs' 的科研主题。它们共同构成独一无二的指纹。

引用此