𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Fulkerson′s Conjecture and Circuit Covers

✍ Scribed by G.H. Fan; A. Raspaud

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
206 KB
Volume
61
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Proofs of Two Minimum Circuit Cover Conj
Proofs of Two Minimum Circuit Cover Conjectures
✍ Genghua Fan 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 260 KB

Let G be a 2-edge-connected graph with m edges and n vertices. The following two conjectures are proved in this paper. (i) The edges of G can be covered by circuits of total length at most m+n&1. (ii) The vertices of G can be covered by circuits of total length at most 2(n&1), where n 2. 1998 Acad

Circuit Coverings of Graphs and a Conjec
Circuit Coverings of Graphs and a Conjecture of Pyber
✍ G.H. Fan 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 260 KB

An equivalent statement of the circuit double cover conjecture is that every bridgeless graph \(G\) has a circuit cover such that each vertex \(v\) of \(G\) is contained in at most \(d(v)\) circuits of the cover, where \(d(v)\) is the degree of \(v\). Pyber conjectured that every bridgeless graph \(

The equivalence of two conjectures of Be
The equivalence of two conjectures of Berge and Fulkerson
✍ G. Mazzuoccolo 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 65 KB

Let G be a bridgeless cubic graph. Fulkerson conjectured that there exist six 1-factors of G such that each edge of G is contained in exactly two of them. Berge conjectured that the edge-set of G can be covered with at most five 1-factors. We prove that the two conjectures are equivalent.

Tutte′s 3-Flow Conjecture and Short Cycl
Tutte′s 3-Flow Conjecture and Short Cycle Covers
✍ G.H. Fan 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 285 KB

In this paper we prove: (i) If a graph \(G\) has a nowhere-zero 6 -llow \(\phi\) such that \(\left|E_{\text {odd }}(\phi)\right| \geqslant \frac{2}{3}|E(G)|\), then \(G\) has a cycle cover in which the sum of the lengths of the cycles in the cycle cover is at most \(\frac{44}{27}|E(G)|\), where \(E_

One or Two Disjoint Circuits Cover Indep
One or Two Disjoint Circuits Cover Independent Edges: Lovász–Woodall Conjecture
✍ Ken-ichi Kawarabayashi 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 408 KB

In this paper, we prove the following theorem: Let L be a set of k independent edges in a k-connected graph G. If k is even or G -L is connected, then there exist one or two disjoint circuits containing all the edges in L. This theorem is the first step in the proof of the conjecture of L.

On possible counterexamples to Negami's
On possible counterexamples to Negami's planar cover conjecture
✍ Petr Hliněný; Robin Thomas 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 281 KB

## Abstract A simple graph **__H__** is a cover of a graph **__G__** if there exists a mapping φ from **__H__** onto **__G__** such that φ maps the neighbors of every vertex υ in **__H__** bijectively to the neighbors of φ (υ) in **__G__**. Negami conjectured in 1986 that a connected graph has a fi