A common generalization of Chvátal-Erdősʹ and Fraisseʹs sufficient conditions for hamiltonian graphs Original Research Article

Let G = (V, E) be a k-connected graph of order n. For S ⊂ V, let N(S) be its neighborhood set and let J(S) = {u ∉ S | N(u) ⊇ S} if |S| ⩾ 2 and J(S) = 0 otherwise. If there exists some s, 1 ⩽ s ⩽ k, such that every independent set X of s + 1 vertices has a vertex u satisfying |N(Xβ{u})| + |N(u) ∪ J(X)β{u})| ⩾ n, then G is hamiltonian. From this main theorem, we derive new sufficient conditions for hamiltonian graphs. Some of these results are improvements and/or generalizations of various known results. In particular, sufficient conditions of Ore (1960), Chvátal and Erdős (1972), Fraisse (1986) and E. Flandrin et al. (1991) are easily derived.