✦ LIBER ✦

Perfect path double covers of graphs

✍ Scribed by J. A. Bondy

Publisher: John Wiley and Sons
Year: 1990
Tongue: English
Weight: 513 KB
Volume: 14
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190140213

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Packings and perfect path double covers

Packings and perfect path double covers of maximal planar graphs

✍ Karen Seyffarth 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 817 KB

Seyffarth, K., Packings and perfect path double covers of maximal planar graphs, Discrete Mathematics 117 (1993) 1833195. A maximal planar graph is a simple planar graph in which every face is a triangle, and a perfect packing of such a graph by 2-cliques and facial triangles corresponds to a parti

Perfect path double covers in every simp

Perfect path double covers in every simple graph

✍ Hao Li 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 229 KB

## 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 c

Path covers of weighted graphs

✍ Genghua Fan 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB

Let (G, w ) denote a simple graph G with a weight function w : €(G) -{0,1,2}. A path cover of (G, w ) is a collection of paths in G such that every edge e is contained in exactly w(e) paths of the collection. For a vertex u , w ( v ) is the sum of the weights of the edges incident with U ; U is call

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

Counting double covers of graphs

✍ M. Hofmeister 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB

Any group of automorphisms of a graph G induces a notion of isomorphism between double covers of G. The corresponding isomorphism classes will be counted.

Ki-covers. II. Ki-perfect graphs

✍ Michele Conforti; Derek Gordon Corneil; Ali Ridha Mahjoub 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 675 KB