Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs

Szczegóły
Opis

Tytuł:: Forbidden Subgraphs for Hamiltonicity of 1-Tough Graphs
Autorzy:: Li, Binlong
Broersma, Hajo J.
Zhang, Shenggui
Powiązania:: https://bibliotekanauki.pl/articles/31340596.pdf
Data publikacji:: 2016-11-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: forbidden subgraph
1-tough graph
H-free graph
hamiltonian graph
Źródło:: Discussiones Mathematicae Graph Theory; 2016, 36, 4; 915-929
2083-5892
Język:: angielski
Prawa:: CC BY-NC-ND: Creative Commons Uznanie autorstwa - Użycie niekomercyjne - Bez utworów zależnych 4.0
Dostawca treści:: Biblioteka Nauki
: Artykuł

Przejdź do źródła

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₁ ∪ P₄ as the only open case.

Informacja

Powiązane pozycje