Forbidden triples implying Hamiltonicity: for all graphs
Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson · Discussiones Mathematicae Graph Theory · 2004
In [2], Brousek characterizes all triples of graphs, G 1 , G 2 , G 3 , with G i = K 1,3 for some i = 1, 2, or 3, such that all G 1 G 2 G 3 -free graphs contain a hamiltonian cycle.In [6], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G 1 , G 2 , G 3 , none of which is a K 1,s , s ≥ 3 such that G 1 , G 2 , G 3 -free graphs of sufficiently large order contain a hamiltonian cycle.In this paper, a characterization will be given of all triples G 1 , G 2 , G 3 with none being K 1,3 , such that all G 1 G 2 G 3 -free graphs are hamiltonian.This result, together with the triples given by Brousek, completely characterize the forbidden triples