𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Perfect double covers with paths of length four

✍ Scribed by Heinrich, K.; Horak, P.; Wallis, W.; Yu, Qinglin

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
347 KB
Volume
21
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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, Inc.

πŸ“œ SIMILAR VOLUMES

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

Small cycle double covers of products I:
Small cycle double covers of products I: Lexicographic product with paths and cycles
✍ R. J. Nowakowski; K. Seyffarth πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 243 KB

## Abstract Bondy conjectured that every simple bridgeless graph has a small cycle double cover (SCDC). We show that this is the case for the lexicographic products of certain graphs and along the way for the Cartesian product as well. Specifically, if __G__ does not have an isolated vertex then __

Double coverings of 2-paths by Hamilton
Double coverings of 2-paths by Hamilton cycles*
✍ Midori Kobayashi; Nobuaki Mutoh; Kiyasu-Zen'iti; Gisaku Nakamura πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 117 KB

## Abstract A double Dudeney set in __K~n~__ is a multiset of Hamilton cycles in __K~n~__ having the property that each 2‐path in __K~n~__ lies in exactly two of the cycles. A double Dudeney set in __K~n~__ has been constructed when __n__ β‰₯ 4 is even. In this paper, we construct a double Dudeney se

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

Partitions of a graph into paths with pr
Partitions of a graph into paths with prescribed endvertices and lengths
✍ Hikoe Enomoto; Katsuhiro Ota πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 95 KB πŸ‘ 3 views

For a graph G, let ' 2 (G ) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| n i 1 k a i and ' 2 (G ) ! n k Γ€ 1, then for any k vertices v 1 , v 2 , F F F , v k in G, there exist vertex-disjoint paths P 1 , P 2 , F F F , P k such that |V (P i )| a i and v