More on decompositions of edge-colored complete graphs
type: Item
instance of: scholarly article
title: More on decompositions of edge-colored complete graphs
zbMATH Open document ID: 1143.05064
author: Anna Draganova
author: Yukiyasu Mutoh
author: Richard M. Wilson
published in: Discrete Mathematics
publication date: 2008-05-29T00:00:00Z
review text: Let \(R\) be a set of \(r\) colors and \(\mathcal G\) a family of graphs whose edges are colored with colors from \(R\) such that for every \(G\in \mathcal G\) any two vertices of \(G\) are joined by at most one edge colored \(i\) for any \(i\in R\). \(K^{(r)}_{n}\) denotes the complete graph on \(n\) vertices where every two vertices are joined by \(r\) edges of all \(r\) colors of \(R\). A \(\mathcal G\)-decomposition of \(K^{(r)}_{n}\) is a collection \(\mathcal D\) of subgraphs of \(K^{(r)}_{n}\), each of which is a color-preserving isomorphic copy of some graph in \(\mathcal G\), so that every edge of \(K^{(r)}_{n}\) belongs to exactly one graph of \(\mathcal D\). Necessary and asymptotically sufficient conditions on \(n\) are given for the existence of a \(\mathcal G\)-decomposition. This result is an extension of the classical result by \textit{R. M. Wilson} [``Decompositions of the complete graphs into subgraphs isomorphic to a given graph'', Proc. 5th Br. comb. Conf., Aberdeen 1975, 647--659 (1976; Zbl 0322.05116)] on \(G\)-decompositions of simple complete graphs.
reviewed by: Dalibor Fronček
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05B05
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 05D10
zbMATH DE Number: 5280729
zbMATH Keywords: decomposition
zbMATH Keywords: complete graph
zbMATH Keywords: edge-colored
MaRDI profile type: Publication
full work available at URL: j.disc.2007.08.044
OpenAlex ID: W1971367333
cites work: Decompositions of edge-colored complete graphs
cites work: {2, 3}‐perfect m‐cycle systems are equationally defined for m = 5, 7, 8, 9, and 11 only
cites work: Q3818127
cites work: An existence theory for pairwise balanced designs. II: Structure of PBD- closed sets and the existence conjectures
cites work: An existence theory for pairwise balanced designs. III: Proof of the existence conjectures
cites work: Q4083463
DOI: 10.1016/J.DISC.2007.08.044
Recommended article: Q4798525
Recommended article: On the existence and embedding of edge-coloured graph decompositions.
Recommended article: Q4886182
Recommended article: On smallest regular graphs with a given isopart
Recommended article: Regular packings of regular graphs
Recommended article: Decomposing Graphs into Edges and Triangles
Recommended article: Q3752404
Recommended article: Q4439361
Recommended article: Q3474665
Recommended article: A note on the Erd\"os-Faber-Lov\'asz Conjecture: quasigroups and complete digraphs
description: scientific article; zbMATH DE number 5280729