On eulerian and regular perfect path double covers of graphs Original Research Article

A perfect path double cover (PPDC) of a graph G is a family image of paths of G such that every edge of G belongs to exactly two paths of image and each vertex of G occurs exactly twice as an endpoint of a path in image. Li (J. Graph Theory 14 (1990) 645–650) has shown that every simple graph has a PPDC. A regular perfect path double cover (RPPDC) of a graph G is a PPDC of G in which all paths are of the same length. For a path double cover image of a graph G, the associated graph image of image is defined as a graph having the same vertex set as G, with two vertices x and y adjacent if and only if there is a path in image with endpoints x and y. An eulerian perfect path double cover (EPPDC) of a graph G is a PPDC of G whose associated graph is a cycle. If a PPDC is both eulerian and regular, it is called an ERPPDC. In this paper, we will discuss EPPDCs and RPPDCs for certain types of graphs. In particular, we will describe a construction for an ERPPDC of the line graph of a complete graph.