Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs

• Autorzy: Binlong Li , Hajo J. Broersma , Shenggui Zhang
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

forbidden subgraph; 1-tough graph; H-free graph; hamiltonian graph

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 4
• Strony: 915-929

Daty

wydano

2016-11-01

otrzymano

2015-03-18

poprawiono

2016-01-06

zaakceptowano

2016-01-07

online

2016-10-21

Twórcy

autor

Binlong Li

• Department of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi’an, Shaanxi 710072, P.R.
• European Centre of Excellence NTIS 306 14 Pilsen, Czech Republic

autor

Hajo J. Broersma

• Faculty of EEMCS, University of Twente 7500 AE Enschede,

autor

Shenggui Zhang

• Department of Applied Mathematics, School of Science Northwestern Polytechnical University Xi’an, Shaanxi 710072, P.R.,

Identyfikatory

DOI

10.7151/dmgt.1897