POTENTIAL FORBIDDEN TRIPLES IMPLYING HAMILTONICITY: FOR SUFFICIENTLY LARGE GRAPHS

In [2], Brousek characterizes all triples of connected graphs, G1, G2, G3, with Gi = K1,3 for some i = 1, 2, or 3, such that all G1G2G3-free graphs contain a hamiltonian cycle. In [8], Faudree, Gould, Ja-cobson and Lesniak consider the problem of finding triples of graphs G1, G2, G3, none of which is a K1,s, s ≥ 3 such that G1G2G3-free graphs of sufficiently large order contain a hamiltonian cycle. In [6], a characterization was given of all triples G1, G2, G3 with none being K1,3, such that all G1G2G3-free graphs are hamiltonian. This result, together with the triples given by Brousek, completely characterize the forbidden triples G1, G2, G3 such that all G1G2G3-free graphs are hamiltonian. In this paper we consider the question of which triples (including K1,s, s ≥ 3) of forbidden subgraphs potentially imply all sufficiently large graphs are hamiltonian. For s ≥ 4 we characterize these families