✦ LIBER ✦

Cycle-cocycle partitions and faithful cycle covers for locally finite graphs

✍ Scribed by Henning Bruhn; Reinhard Diestel; Maya Stein

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 112 KB
Volume: 50
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20101

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

By a result of Gallai, every finite graph G has a vertex partition into two parts each inducing an element of its cycle space. This fails for infinite graphs if, as usual, the cycle space is defined as the span of the edge sets of finite cycles in G. However, we show that, for the adaptation of the cycle space to infinite graphs recently introduced by Diestel and Kühn (which involves infinite cycles as well as finite ones), Gallai's theorem extends to locally finite graphs. Using similar techniques, we show that if Seymour's faithful cycle cover conjecture is true for finite graphs then it also holds for locally finite graphs when infinite cyles are allowed in the cover, but not otherwise. We also consider extensions to graphs with infinite degrees. © 2005 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

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