Perfect Path Double Covers of Graphs
|Affiliation:||Combinatorics and Optimization, University of Waterloo|
|Room:||Mathematics and Computer Building (MC) 5168|
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.
200 University Avenue West
Waterloo, ON N2L 3G1