- Tytuł:
- Potential forbidden triples implying hamiltonicity: for sufficiently large graphs
- Autorzy:
-
Faudree, Ralph
Gould, Ronald
Jacobson, Michael - Powiązania:
- https://bibliotekanauki.pl/articles/744366.pdf
- Data publikacji:
- 2005
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
hamiltonian
forbidden subgraph
claw-free
induced subgraph - Opis:
- In [1], Brousek characterizes all triples of connected graphs, G₁,G₂,G₃, with $G_i = K_{1,3}$ for some i = 1,2, or 3, such that all G₁G₂ G₃-free graphs contain a hamiltonian cycle. In [8], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁,G₂,G₃, none of which is a $K_{1,s}$, s ≥ 3 such that G₁G₂G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In [6], a characterization was given of all triples G₁,G₂,G₃ with none being $K_{1,3}$, such that all G₁G₂G₃-free graphs are hamiltonian. This result, together with the triples given by Brousek, completely characterize the forbidden triples G₁,G₂,G₃ such that all G₁G₂G₃-free graphs are hamiltonian. In this paper we consider the question of which triples (including $K_{1,s}$, s ≥ 3) of forbidden subgraphs potentially imply all sufficiently large graphs are hamiltonian. For s ≥ 4 we characterize these families.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2005, 25, 3; 273-289
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł