A Closure Lemma for tough graphs and Hamiltonian degree conditions
Time: 14:30 -- Location: LRI, 445
summary: A graph G is Hamiltonian if there 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 d_1,d_2,…,d_n and let t be a positive integer at most 4. If G is t-tough and if for every integer i in [t,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.