𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Perfect path double covers in every simple graph

✍ Scribed by Hao Li

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
229 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We prove in this paper that every simple graph G admits a perfect path double cover (PPDC), i.e., a set of paths of G such that each edge of G belongs to exactly two of the paths and each vertex of G is an end of exactly two of the paths, where a path of length zero is considered to have (identical) ends. This was conjectured by A. Bondy in 1988.

πŸ“œ SIMILAR VOLUMES

Perfect double covers with paths of leng
Perfect double covers with paths of length four
✍ Heinrich, K.; Horak, P.; Wallis, W.; Yu, Qinglin πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 347 KB πŸ‘ 1 views

It is shown that for any 4-regular graph G there is a collection F of paths of length 4 such that each edge of G belongs to exactly two of the paths and each vertex of G occurs exactly twice as an endvertex of a path of y. This proves a special case of a conjecture of Bondy. 0 1996 John Wiley & Sons

Recognizing triangle-free graphs with in
Recognizing triangle-free graphs with induced path-cycle double covers is NP-complete
✍ Jacobson, Michael S.; KοΏ½zdy, AndrοΏ½ E.; Lehel, Jen? πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 250 KB πŸ‘ 2 views

An induced path-cycle double cover (IPCDC) of a simple graph G is a family F Γ… {F 1 , . . . , F k } of induced paths and cycles of G such that if F i ʝ F j x M, then F i ʝ F j is a vertex or an edge, for i x j, each edge of G appears in precisely two of the F i 's, and each vertex of G appears in pr