Premium
Perfect path double covers of graphs
Author(s) -
Bondy J. A.
Publication year - 1990
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190140213
Subject(s) - combinatorics , mathematics , discrete mathematics , vertex (graph theory) , graph
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.