More on decompositions of edge-colored complete graphs (Q924985): Difference between revisions

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.