✦ LIBER ✦

Circuit Coverings of Graphs and a Conjecture of Pyber

✍ Scribed by G.H. Fan

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 260 KB
Volume: 65
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1995.1040

No coin nor oath required. For personal study only.

✦ Synopsis

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 (G) has a circuit cover such that every vertex of (G) is contained in at most (\Delta(G)) circuits of the cover, where (\Delta(G)) is the maximum degree of (G). This paper affirms Pyber's conjecture by establishing an intermediate result, namely 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 if (d(v) \geqslant 3) and in at most three circuits of the cover if (d(v)=2). Our proofs rely on results on integer flows. (c) 1995 Academic Press. Inc.

📜 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 decompositions of join-covered g

Circuit decompositions of join-covered graphs

✍ Marcelo H. de Carvalho; C. H. C. Little 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB

## Abstract In this paper, we focus our attention on join‐covered graphs, that is, ±1‐weighted graphs, without negative circuits, in which every edge lies in a zero‐weight circuit. Join covered graphs are a natural generalization of matching‐covered graphs. Many important properties of matching cov

Shortest Circuit Covers of Cubic Graphs

✍ B. Jackson 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 298 KB

We show that the edge set of a bridgeless cubic graph \(G\) can be covered with circuits such that the sum of the lengths of the circuits is at most \(\frac{64}{39}|E(G)|\). Stronger results are obtained for cubic graphs of large girth. 1994 Academic Press, Inc.

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

A note on coverings of plane graphs

✍ Eduardo Rivera-Campo 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB 👁 1 views

## Abstract For any plane graph __G__ the number of edges in a minimum edge covering of the faces of __G__ is at most the vertex independence number of __G__ and the numbre of vertices in a minimum vertex covering of the faces of __G__ is at most the edge independence number of __G__. © 1995 John W

Total matchings and total coverings of g

Total matchings and total coverings of graphs

✍ Y. Alavi; M. Behzad; L. M. Lesniak-Foster; E. A. Nordhaus 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 280 KB

## Abstract In graph theory, the related problems of deciding when a set of vertices or a set of edges constitutes a maximum matching or a minimum covering have been extensively studied. In this paper we generalize these ideas by defining total matchings and total coverings, and show that these set