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\setminus S\) is at most \(\lvert S \rvert / t\). We extended a theorem of Hoàng by proving the following: Let \(G\) be a graph with degree sequence \(d_1,d_2,\dots, d_n\) and let \(t\) be a positive integer at most 6. If \(G\) is \(t\)-tough and if \(\forall i, t \le i < n/2\), \(d_i \le i \implies d_{n−i+t} \ge 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 @GREYC