Seminar - Cheolwon Heo

Perfect Path Double Covers of Graphs

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.