𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by André Raspaud

Publisher
John Wiley and Sons
Year
1991
Tongue
English
Weight
234 KB
Volume
15
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

The size of graphs without nowhere-zero
The size of graphs without nowhere-zero 4-flows
✍ Hong-Jian Lai 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 428 KB 👁 1 views

Let G be a 2-edge-connected simple graph with order n. We show that if IV(G)l 5 17, then either G has a nowhere-zero 4-flow, or G is contractible to the Petersen graph. We also show that for n large, if I€(G)J L (' 2 17) + 34, then either G has a nonwhere-zero 4-flow, or G can be contracted to the P

A characterization of well-covered graph
A characterization of well-covered graphs that contain neither 4- nor 5-cycles
✍ A. Finbow; B. Hartnell; R. J. Nowakowski 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 434 KB 👁 1 views

## Abstract A graph is well covered if every maximal independent set has the same cardinality. A vertex __x__, in a well‐covered graph __G__, is called extendable if __G – {x}__ is well covered and β(__G__) = β(__G – {x}__). If __G__ is a connected, well‐covered graph containing no 4‐ nor 5‐cycles