✦ LIBER ✦

Covering a graph with cycles

✍ Scribed by Hong Wang

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 444 KB
Volume: 20
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190200209

No coin nor oath required. For personal study only.

✦ Synopsis

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 triangles. © 1995, John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Covering a graph with cycles passing thr

Covering a graph with cycles passing through given edges

✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 91 KB 👁 2 views

We propose a conjecture: for each integer k ≥ 2, there exists N (k) such that if G is a graph of order n ≥ N (k) and d(x) + d(y) ≥ n + 2k -2 for each pair of nonadjacent vertices x and y of G, then for any k independent edges e 1 , . . . , e k of G, there exist If this conjecture is true, the condi

Cycle covers of graphs with a nowhere-ze

Cycle covers of graphs with a nowhere-zero 4-flow

✍ André Raspaud 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 234 KB 👁 1 views

## Abstract It is shown that the edges of a simple graph with a nowhere‐zero 4‐flow can be covered with cycles such that the sum of the lengths of the cycles is at most |__E__(__G__)| + |__V__(__G__)| −3. This solves a conjecture proposed by G. Fan.

Covering the vertices of a graph by cycl

Covering the vertices of a graph by cycles of prescribed length

✍ D. Amar; I. Fournier; A. Germa 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 321 KB

The main theorem of that paper is the following: let G be a graph of order n, of size at least (nZ -3n + 6 ) / 2 . For any integers k, n,, n2,. . . , nk such that n = n, + n2 + ... + nk and n, 2 3, there exists a covering of the vertices of G by disjoint cycles (C,),=,..,k with ICjl = n,, except whe

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.

Cycle and cocycle coverings of graphs

✍ Sean McGuinness 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB

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

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)__|.