Perfect path double covers of graphs |
| |
Authors: | J. A. Bondy |
| |
Abstract: | A perfect path double cover (PPDC) of a graph G on n vertices is a family ?? of n paths of G such that each edge of G belongs to exactly two members of ?? and each vertex of G occurs exactly twice as an end of a path of ??. We propose and study the conjecture that every simple graph admits a PPDC. Among other things, we prove that every simple 3-regular graph admits a PPDC consisting of paths of length three. |
| |
Keywords: | |
|
|