Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs
Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs
复制标题
DOI：
10.7151/dmgt.1897
复制
发表时间：
2016-11
影响因子：
0.7
通讯作者：
H. Broersma;Binlong Li;Shenggui Zhang
中科院分区：
文献类型：
--
作者：
H. Broersma;Binlong Li;Shenggui Zhang
图G称为1-坚韧图，如果对图G的每个顶点割S，G的−S的分支个数不超过|S|。1-坚韧是图是哈密顿图的一个明显的必要条件，但一般而言这并不是充分条件。我们研究刻画所有图H使得每个1-坚韧H-Free图都是哈密顿图的问题。我们几乎得到了这个问题的一个完全解，留下H=K1∪P4是唯一未解决的情形。
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.