Title : A Closure Lemma for tough graphs and Hamiltonian degree conditions
|Institution:||Wilfrid Laurier University|
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