Decompositions of edge-colored complete graphs
type: Item
instance of: scholarly article
title: Decompositions of edge-colored complete graphs
zbMATH Open document ID: 0937.05064
author: Richard M. Wilson
author: Esther R. Lamken
published in: Journal of Combinatorial Theory. Series A
publication date: 2000-06-04T00:00:00Z
review text: In this paper finite edge-\(r\)-colored directed graphs are considered. For a vertex \(x\) of an edge-\(r\)-colored digraph \(G\), the degree-vector of \(x\) is defined as the \(2r\)-vector \[ \tau (x)=(in_{1}(x),out_{1}(x),\ldots ,in_{r}(x),out_{r}(x)) \] where \(in_{j}(x)\) and \(out_{j}(x)\) denote, respectively, the indegree and outdegree of vertex \(x\) in the spanning subgraph of \(G\) determined by the edges of color \(j\), \(1\leq j\leq r\). Let \(\alpha (G)\) be the greatest common divisor of the integers \(t\) such that the \(2r\)-vector \((t,\ldots ,t)\) is an integral linear combination of the vectors \(\tau (x)\) as \(x\) ranges over \(V(G)\). A very general asymptotic existence theorem for decompositions of edge-colored complete graphs into prespecified edge-colored subgraphs is proved. A special case of this theorem is the following one: Let \(G\) be a simple edge-\(r\)-colored digraph with \(m\) edges each of \(r\) different colors. There exists a constant \(n_{0}=n_{0}(G)\) such that the complete edge-\(r\)-colored digraph with \(rn(n-1)\) edges \(K_{n}^{(r)}\) admits a \(G\)-decomposition for all integers \(n\geq n_{0}\) that satisfy the following conditions: \(n(n-1)\equiv 0\pmod m\) and \(n-1\equiv 0\pmod{\alpha (G)}\). Since many combinatorial design problems fall within this framework, this provides new proofs of the asymptotic existence of resolvable designs, near resolvable designs, group divisible designs, and grid designs. This important paper concludes with two further applications: the asymptotic existence of skew Room \(d\)-cubes and the asymptotic existence of \((v,k,1)\)-BIBDs with any group of order \(k-1\) as an automorphism group.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05B15
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05B05
zbMATH DE Number: 1422982
zbMATH Keywords: edge-\(r\)-colored directed graph
zbMATH Keywords: decomposition
zbMATH Keywords: resolvable design
zbMATH Keywords: near resolvable design
zbMATH Keywords: group divisible design
zbMATH Keywords: grid design
zbMATH Keywords: Room \(d\)-cube
zbMATH Keywords: automorphism group
zbMATH Keywords: asymptotic existence theorem
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
OpenAlex ID: W2051968426
cites work: Q4876928
cites work: Q3996173
cites work: Q4862341
cites work: Q4876990
cites work: Q3480047
cites work: Q4091962
cites work: Q3998644
cites work: Self-orthogonal latin squares of all orders 𝑛≠2,3,6
cites work: Q3879243
cites work: On colored designs. II
cites work: On colored designs. I
cites work: Edge-coloured designs with block size four
cites work: Existence results for near resolvable designs
cites work: On complementary decompositions of the complete graph
cites work: The module structure of integral designs
cites work: Q5181706
cites work: Q3715120
cites work: Q4876959
cites work: Q4026150
cites work: Steiner pentagon systems
cites work: Q4221870
cites work: Q5661892
cites work: On reverse Steiner triple systems
cites work: Q3818127
cites work: The spectrum of nested Steiner triple systems
cites work: Q3952110
cites work: The existence of reverse Steiner triple systems
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: Cyclotomy and difference families in elementary Abelian groups
cites work: Q4083463
cites work: Q4071247
cites work: Q4774057
DOI: 10.1006/JCTA.1999.3005
description: scientific article; zbMATH DE number 1422982