✦ LIBER ✦

Minimum cycle coverings and integer flows

✍ Scribed by Cun-Quan Zhang

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

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

It was conjectured by Fan that if a graph G = (V,E) has a nowhere‐zero 3‐flow, then G can be covered by two even subgraphs of total size at most |V| + |E| ‐ 3. This conjecture is proved in this paper. It is also proved in this paper that the optimum solution of the Chinese postman problem and the solution of minimum cycle covering problem are equivalent for any graph admitting a nowhere‐zero 4‐flow.

📜 SIMILAR VOLUMES

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.

Integer flows

✍ D. H. Younger 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 404 KB

A k-flow is an assignment of edge directions and integer weights in the range 1, ..., k -1 to the edges of an undirected graph so that at each vertex the flow in is equal to the flow out. This paper gives a polynomial algorithm for finding a 6-flow that applies uniformly to each graph. The algorithm

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

Resolvable minimum coverings with quadru

Resolvable minimum coverings with quadruples

✍ E. R. Lamken; W. H. Mills; R. S. Rees 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 460 KB

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

New polynomial-time cycle-canceling algo

New polynomial-time cycle-canceling algorithms for minimum-cost flows

✍ P. T. Sokkalingam; Ravindra K. Ahuja; James B. Orlin 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 227 KB