𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Circuit decompositions of join-covered graphs

✍ Scribed by Marcelo H. de Carvalho; C. H. C. Little

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
137 KB
Volume
62
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 covered graphs, such as the existence of a canonical partition, tight cut decomposition and ear decomposition, have been generalized to join covered graphs by A. Sebő [5]. In this paper we prove that any two edges of a join‐covered graph lie on a zero‐weight circuit (under an equivalent weighting), generalize this statement to an arbitrary number of edges, and characterize minimal bipartite join‐covered graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 220–233, 2009

📜 SIMILAR VOLUMES

Compatible circuit decompositions of 4-r
Compatible circuit decompositions of 4-regular graphs
✍ Herbert Fleischner; François Genest; Bill Jackson 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 210 KB

## Abstract A transition system __T__ of an Eulerian graph __G__ is a family of partitions of the edges incident to each vertex of __G__ into transitions, that is, subsets of size two. A circuit decomposition $\cal C$ of __G__ is compatible with __T__ if no pair of adjacent edges of __G__ is both a

Shortest Circuit Covers of Cubic Graphs
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.

Atoll decompositions of graphs
Atoll decompositions of graphs
✍ Fred Buckley 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 352 KB

## Abstract An island decomposition of a graph __G__ consists of a set of vertex‐disjoint paths which cover the vertex set of __G.__ If the endpoints of the paths are mutually nonadjacent, then we have an atoll decomposition. We characterize graphs requiring two paths in an island decomposition yet

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

Optimal Ear Decompositions of Matching C
Optimal Ear Decompositions of Matching Covered Graphs and Bases for the Matching Lattice
✍ Marcelo H. de Carvalho; Cláudio L. Lucchesi; U.S.R. Murty 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 225 KB

A Petersen brick is a graph whose underlying simple graph is isomorphic to the Petersen graph. For a matching covered graph G, b(G) denotes the number of bricks of G, and p(G) denotes the number of Petersen bricks of G. An ear decomposition of G is optimal if, among all ear decompositions of G, it u