✦ LIBER ✦

Cycle and cocycle coverings of graphs

✍ Scribed by Sean McGuinness

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 161 KB
Volume: 65
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20480

No coin nor oath required. For personal study only.

✦ Synopsis

In this article, we show that for any simple, bridgeless graph G on n vertices, there is a family C of at most n-1 cycles which cover the edges of G at least twice. A similar, dual result is also proven for cocycles namely: for any loopless graph G on n vertices and edges having cogirth g * ≥ 3 and k(G) components, there is a family of at most -n+k(G) cocycles which cover the edges of G at least twice.

📜 SIMILAR VOLUMES

Cycle-cocycle partitions and faithful cy

Cycle-cocycle partitions and faithful cycle covers for locally finite graphs

✍ Henning Bruhn; Reinhard Diestel; Maya Stein 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

## Abstract By a result of Gallai, every finite graph __G__ has a vertex partition into two parts each inducing an element of its cycle space. This fails for infinite graphs if, as usual, the cycle space is defined as the span of the edge sets of finite cycles in __G__. However, we show that, for t

Minimum cycle covers of graphs

✍ Fan, Genghua 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB 👁 1 views

Some new results on minimum cycle covers are proved. As a consequence, it is obtained that the edges of a bridgeless graph G can be covered by cycles of total length at most |E(G)| + 25 24 (|V (G)| -1), and at most |E(G)| + |V (G)| -1 if G contains no circuit of length 8 or 12.

Closure, 2-factors, and cycle coverings

Closure, 2-factors, and cycle coverings in claw-free graphs

✍ Ryj�?ek, Zden?k; Saito, Akira; Schelp, R. H. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 239 KB 👁 3 views

In this article, we study cycle coverings and 2-factors of a claw-free graph and those of its closure, which has been defined by the first author (On a closure concept in claw-free graphs, J Combin Theory Ser B 70 (1997), 217-224). For a claw-free graph G and its closure cl(G), we prove: ( 1 (2) G

Pentagons and cycle coverings

✍ Hong Wang 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB

## Abstract Let __G__ be a graph of order __n__ ≥ 5__k__ + 2, where __k__ is a positive integer. Suppose that the minimum degree of __G__ is at least ⌈(__n__ + __k__)/2⌉. We show that __G__ contains __k__ pentagons and a path such that they are vertex‐disjoint and cover all the vertices of __G__. M

Short cycle covers of cubic graphs

✍ Genghua Fan 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 461 KB

## Abstract Let __G__ be a bridgeless cubic graph. We prove that the edges of __G__ can be covered by circuits whose total length is at most (44/27) |__E(G)__|, and if Tutte's 3‐flow Conjecture is true, at most (92/57) |__E(G)__|.

Covering a graph with cycles

✍ Hong Wang 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 444 KB

## Abstract Let __k__ and __n__ be two integers such that __k__ ≥ 0 and __n__ ≥ 3(__k__ + 1). Let __G__ be a graph of order __n__ with minimum degree at least ⌈(__n__ + __k__)/2⌉. Then __G__ contains __k__ + 1 independent cycles covering all the vertices of __G__ such that __k__ of them are triangl