✦ LIBER ✦

A result on decompositions of regular graphs

✍ Scribed by Xiang-Ying Su

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 224 KB
Volume: 105
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90156-a

No coin nor oath required. For personal study only.

✦ Synopsis

A result on decompositions of regular graphs, Discrete Mathematics 105 (1992) 323-326. We prove that for any connected graph G and any integer r which is a common multiple of the degrees of the vertices in G, there exists a connected, r-regular, and G-decomposable graph H such that x(H) = x(G) and o(H) = w(G), where x and w are the chromatic number and the clique number, respectively. Also we give a bound for the minimum order among all such graphs.

📜 SIMILAR VOLUMES

Decompositions of regular bipartite grap

Decompositions of regular bipartite graphs

✍ Michael S. Jacobson; Miroslaw Truszczyński; Zsolt Tuza 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 692 KB

In this paper we discuss isomorphic decompositions of regular bipartite graphs into trees and forests. We prove that: (1) there is a wide class of r-regular bipartite graphs that are decomposable into any tree of size r, (2) every r-regular bipartite graph decomposes into any double star of size r,

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

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

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

Decompositions of regular graphs into Kn

Decompositions of regular graphs into Knc ∨ 2K2

✍ R. Balakrishnan; R. Sampathkumar 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 437 KB

The join K~ V2K2 is the graph obtained by taking a copy ofK, ~ and two disjoint copies of K2, disjoint from K c, and joining every vertex of K, c to every vertex of 2K2. In this paper we show that for each positive integer n, the graph K, ~ V 2/(2 admits a p-valuation and has gracefulness 4n + 3. Fu

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