Séminaire Algorithmique : « Tough graphs and Hamiltonian degree conditions », Cléophée Robin (GREYC, Caen)

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 a theorem of Hoàng by proving the following : Let G be a graph with degree sequence d₁,d₂,…,d_n and let t be a positive integer at most 6. If G is t-tough and if ∀ i, t ≤ i <n/2, d_i ≤ i ⇒ d_n−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.

Cléophée Robin website