Wednesday, February 12, 2014 — 3:30 PM EST

Perfect Path Double Covers of Graphs

Speaker: Cheolwon Heo
Affiliation: Combinatorics and Optimization, University of Waterloo
Room: Mathematics and Computer Building (MC) 5168

Abstract: 

A cycle double cover (CDC) of a graph G is a collection C of cycles of G such that each edge of G lies in exactly two cycles of C. There is a well known conjecture of Seymour that every bridgeless graph admits a CDC. Bondy proposed a strong version of this conjecture, namely that every bridgeless graph admits a “small” cycle double cover (SCDC).

A perfect path double cover (PPDC) of a graph G is a collection P of paths of G such that each edge of G lies in exactly two paths of P and each vertex of G occurs exactly twice as an end of a path of P. Bondy conjectured that every simple graph admits a PPDC. He shows that these two conjectures are related by proving that for trigraphs the SCDC and PPDC conjecture are equivalent. In 1990, Li proved the PPDC conjecture. I will also introduce generalizations of the PPDC conjecture and discuss related problems.

Location 
MC - Mathematics & Computer Building
6486
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
31
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
1
2
  1. 2021 (90)
    1. October (2)
    2. September (12)
    3. August (7)
    4. July (10)
    5. June (12)
    6. May (7)
    7. April (9)
    8. March (13)
    9. February (8)
    10. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)