✦ LIBER ✦

Shortest Circuit Covers of Cubic Graphs

✍ Scribed by B. Jackson

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 298 KB
Volume: 60
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1994.1021

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

A note on shortest cycle covers of cubic

A note on shortest cycle covers of cubic graphs

✍ Xinmin Hou; Cun-Quan Zhang 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB 👁 1 views

## Abstract Let __SCC__~3~(__G__) be the length of a shortest 3‐cycle cover of a bridgeless cubic graph __G__. It is proved in this note that if __G__ contains no circuit of length 5 (an improvement of Jackson's (__JCTB 1994__) result: if __G__ has girth at least 7) and if all 5‐circuits of __G_

Short cycle covers of cubic graphs

✍ Genghua Fan 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 461 KB

## Abstract Let __G__ be a bridgeless cubic graph. We prove that the edges of __G__ can be covered by circuits whose total length is at most (44/27) |__E(G)__|, and if Tutte's 3‐flow Conjecture is true, at most (92/57) |__E(G)__|.

Small Circuit Double Covers of Cubic Mul

Small Circuit Double Covers of Cubic Multigraphs

✍ H.J. Lai; X.X. Yu; C.Q. Zhang 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 499 KB

Five Cycle Double Covers of Some Cubic G

Five Cycle Double Covers of Some Cubic Graphs

✍ A. Huck; M. Kochol 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 257 KB

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

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