The complete graph \(t\)-packings and \(t\)-coverings (Q1313352)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The complete graph \(t\)-packings and \(t\)-coverings
scientific article

    Statements

    The complete graph \(t\)-packings and \(t\)-coverings (English)
    0 references
    0 references
    26 January 1994
    0 references
    The main result in this paper is that for any \(t\), \(t \leq {p \choose 2}\), there exist multigraphs \(H_ 1\) and \(H_ 2\) each with \(t\) edges, and multigraphs \(R(H_ 1)\) and \(S(H_ 2)\) with \[ r={p \choose 2} - t \left \lfloor {{p \choose 2} \over t} \right \rfloor \] and \(s=t-r\) edges respectively, so that \(K_ p-R (H_ 1)\) and \(K_ p+S (H_ 2)\) can be decomposed into copies of \(H_ 1\) and \(H_ 2\) respectively. An analogous result is obtained for the complete bipartite graph. Unfortunately the notation used is quite complicated.
    0 references
    0 references
    packings
    0 references
    coverings
    0 references
    edge-decomposition
    0 references
    multigraphs
    0 references
    complete bipartite graph
    0 references
    0 references