A Closure Lemma for tough graphs and Hamiltonian degree conditions - Cléophée Robin

Title : A Closure Lemma for tough graphs and Hamiltonian degree conditions

Abstract: A graph G is hamiltonian if it exists a cycle in G containing all vertices of G exactly once. A graph G is t-tough if, ,for all subsets of vertices S, the number of connected components in G − S is at most |S| / t.

We extended the Theorem of Hoàng by proving the following : Let G be a graph with degree sequence d1,d2,...,dn and let t be a positive integer at most 4. If G is t-tough and if. ∀ I, t ≤ I<n/2, di ≤ I ⇒ dn−i+t  ≥ n−i then G is hamiltonian.

To do this we extend the closure lemma due to Bondy and Chvàtal.

This is joint work with Chình T. Hoàng