✦ LIBER ✦

Regular path decompositions of odd regular graphs

✍ Scribed by Odile Favaron; François Genest; Mekkia Kouider

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 197 KB
Volume: 63
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20413

No coin nor oath required. For personal study only.

✦ Synopsis

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 to a decomposition of the graph into paths of length 3 where the middle edges of the paths coincide with the 1‐factor. We conjecture that existence of a 1‐factor is indeed a sufficient condition for Kotzig's problem. For general odd regular graphs, most 1‐factors appear to be extendable and we show that for the family of simple 5‐regular graphs with no cycles of length 4, all 1‐factors are extendable. However, for d>3 we found infinite families of d‐regular simple graphs with non‐extendable 1‐factors. Few authors have studied the decompositions of general regular graphs. We present examples and open problems; in particular, we conjecture that in planar 5‐regular graphs all 1‐factors are extendable. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 114–128, 2010

📜 SIMILAR VOLUMES

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

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

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

Regular factors of regular graphs

✍ B. Bollobás; Akira Saito; N. C. Wormald 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 242 KB

Given r 3 3 and 1 s A s r, we determine all values of k for which every r-regular graph with edge-connectivity A has a k-factor. Some of the earliest results in graph theory are due to Petersen [8] and concern factors in graphs. Among others, Petersen proved that a regular graph of even degree has a

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.

Smallest regular graphs with prescribed

Smallest regular graphs with prescribed odd girth

✍ Guo-Hui Zhang 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 484 KB 👁 1 views

## Abstract The odd girth of a graph __G__ gives the length of a shortest odd cycle in __G.__ Let __f(k,g)__ denote the smallest __n__ such that there exists a __k__‐regular graph of order __n__ and odd girth __g.__ The exact values of __f(k,g)__ are determined if one of the following holds: __k__