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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom