A Closure Lemma for tough graphs and Hamiltonian degree conditions - Cléophée RobinExport this event to calendar

Monday, March 20, 2023 3:00 PM EDT

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

Event tags 

S M T W T F S
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
  1. 2023 (147)
    1. December (7)
    2. November (17)
    3. October (14)
    4. September (10)
    5. August (7)
    6. July (19)
    7. June (21)
    8. May (12)
    9. April (5)
    10. March (17)
    11. February (10)
    12. January (8)
  2. 2022 (150)
    1. December (8)
    2. November (18)
    3. October (15)
    4. September (11)
    5. August (2)
    6. July (17)
    7. June (17)
    8. May (10)
    9. April (12)
    10. March (18)
    11. February (10)
    12. January (13)
  3. 2021 (103)
  4. 2020 (119)
  5. 2019 (167)
  6. 2018 (136)
  7. 2017 (103)
  8. 2016 (137)
  9. 2015 (136)
  10. 2014 (88)
  11. 2013 (48)
  12. 2012 (39)
  13. 2011 (36)
  14. 2010 (40)
  15. 2009 (40)
  16. 2008 (39)
  17. 2007 (15)