𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Compatible circuit decompositions of 4-regular graphs

✍ Scribed by Herbert Fleischner; François Genest; Bill Jackson

Publisher
John Wiley and Sons
Year
2007
Tongue
English
Weight
210 KB
Volume
56
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 transition of T and consecutive in a circuit of $\cal C$. We give a conjectured characterization of when a 4‐regular graph has a transition system which admits no compatible circuit decomposition. We show that our conjecture is equivalent to the statement that the complete graph on five vertices and the graph with one vertex and two loops are the only essentially 6‐edge‐connected 4‐regular graphs which have a transition system which admits no compatible circuit decomposition. In addition, we show that our conjecture would imply the Circuit Double Cover Conjecture. © Wiley Periodicals, Inc. J. Graph Theory 56: 227–240, 2007

📜 SIMILAR VOLUMES

P4-decompositions of regular graphs
P4-decompositions of regular graphs
✍ Heinrich, Katherine; Liu, Jiping; Yu, Minli 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB 👁 1 views

In this article, we show that every simple r-regular graph G admits a balanced P 4 -decomposition if r ≡ 0(mod 3) and G has no cut-edge when r is odd. We also show that a connected 4-regular graph G admits a P 4 -decomposition if and only if |E(G)| ≡ 0(mod 3) by characterizing graphs of maximum degr

Regular path decompositions of odd regul
Regular path decompositions of odd regular graphs
✍ Odile Favaron; François Genest; Mekkia Kouider 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB

## Abstract Kotzig asked in 1979 what are necessary and sufficient conditions for a __d__‐regular simple graph to admit a decomposition into paths of length __d__ for odd __d__>3. For cubic graphs, the existence of a 1‐factor is both necessary and sufficient. Even more, each 1‐factor is extendable

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

Almost regular edge colorings and regula
Almost regular edge colorings and regular decompositions of complete graphs
✍ Darryn Bryant; Barbara Maenhaut 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract For __k__ = 1 and __k__ = 2, we prove that the obvious necessary numerical conditions for packing __t__ pairwise edge‐disjoint __k__‐regular subgraphs of specified orders __m__~1~,__m__~2~,… ,__m__~t~ in the complete graph of order __n__ are also sufficient. To do so, we present an edge

r-Regular, r-connected decompositions of
r-Regular, r-connected decompositions of complete graphs
✍ H. Fleischner; W. R. Johnstone; A. J. W. Hilton 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB 👁 2 views

If rjn À 1 and rn is even, then K n can be expressed as the union of t nÀ1 r edgedisjoint isomorphic r-regular r-connected factors.