✦ LIBER ✦

Almost regular edge colorings and regular decompositions of complete graphs

✍ Scribed by Darryn Bryant; Barbara Maenhaut

Publisher: John Wiley and Sons
Year: 2008
Tongue: English
Weight: 127 KB
Volume: 16
Category: Article
ISSN: 1063-8539
DOI: 10.1002/jcd.20190

No coin nor oath required. For personal study only.

✦ Synopsis

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‐coloring technique which also yields new proofs of various known results on graph factorizations. For example, a new construction for Hamilton cycle decompositions of complete graphs is given. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 499–506, 2008

📜 SIMILAR VOLUMES

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

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.

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 factorization of graphs

✍ Jin Akiyama; Mikio Kano 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 238 KB

For integers a and b, 0 s a s b, an [a,bl-graph G satisfies a s deg(x,G) s b for every vertex x of G, and an [a.bl-factor is a spanning subgraph its edges can be decomposed into [a,bl-factors. When both k and tare positive integers and s is a nonnegative integer, w e prove that every [(12k + 2)t +

Vertex signatures and edge-4-colorings o

Vertex signatures and edge-4-colorings of 4-regular plane graphs

✍ François Jaeger; Gerhard Koester 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 231 KB 👁 1 views

## Abstract We associate partitions of the edge‐set of a 4‐regular plane graph into 1‐factors or 2‐factors to certain 3‐valued vertex signatures in the spirit of the work by H. Grötzsch [1]. As a corollary we obtain a simple proof of a result of F. Jaeger and H. Shank [2] on the edge‐4‐colorability

A Note on Almost Regular Graphs

✍ M. Of Hofmeister Munich 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 136 KB

It can easily be seen that a conjecture of RUNGE does not hold for a class of graphs whose members will be called "almost regular". This conjecture is replaced by a weaker one, and a classification of almost regular graphs is given.