Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Title : A Closure Lemma for tough graphs and Hamiltonian degree conditions
Speaker: | Cléophée Robin |
Institution: | Wilfrid Laurier University |
Location: | MC 5479 |
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
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within the Office of Indigenous Relations.