Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs

Discussiones Mathematicae Graph Theory

Zhang Shenggui¹  Li Binlong²  Broersma Hajo J.³ 

[1] Department of Applied Mathematics, School of Science Northwestern Polytechnical University Xi’an, Shaanxi 710072, P.R., China;Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi’an, Shaanxi 710072, P.R. China;Faculty of EEMCS, University of Twente 7500 AE Enschede, Netherlands;

关键词: forbidden subgraph;    1-tough graph;    h-free graph;    hamiltonian graph;   

DOI  :  10.7151/dmgt.1897

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown