More on decompositions of edge-colored complete graphs (Q924985)

From MaRDI portal
scientific article
Language Label Description Also known as
English
More on decompositions of edge-colored complete graphs
scientific article

    Statements

    More on decompositions of edge-colored complete graphs (English)
    0 references
    0 references
    0 references
    0 references
    29 May 2008
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    decomposition
    0 references
    complete graph
    0 references
    edge-colored
    0 references
    0 references