✦ LIBER ✦

Proofs of Two Minimum Circuit Cover Conjectures

✍ Scribed by Genghua Fan

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 260 KB
Volume: 74
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1998.1854

No coin nor oath required. For personal study only.

✦ Synopsis

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 Academic Press Conjecture 1.1. The edges of a 2-edge-connected graph G can be covered by circuits of total length at most |E(G)| + |V(G)| &1.

📜 SIMILAR VOLUMES

Bijective proofs of two broken circuit t

Bijective proofs of two broken circuit theorems

✍ Andreas Blass; Bruce Eli Sagan 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 362 KB

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 \(

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.

Covering a Strong Digraph by α−1 Disjoin

Covering a Strong Digraph by α−1 Disjoint Paths: A Proof of Las Vergnas' Conjecture

✍ Stéphan Thomassé 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 83 KB

The Gallai Milgram theorem states that every directed graph D is spanned by :(D) disjoint directed paths, where :(D) is the size of a largest stable set of D. When :(D)>1 and D is strongly connected, it has been conjectured by Las Vergnas that D is spanned by an arborescence with :(D)&1 leaves. The

A Proof of a Conjecture for the Number o

A Proof of a Conjecture for the Number of Ramified Coverings of the Sphere by the Torus

✍ I.P. Goulden; D.M. Jackson 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 136 KB

An explicit expression is obtained for the generating series for the number of ramified coverings of the sphere by the torus, with elementary branch points and prescribed ramification type over infinity. This proves a conjecture of Goulden, Jackson, and Vainshtein for the explicit number of such cov