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

From MaRDI portal





scientific article; zbMATH DE number 490741
Language Label Description Also known as
default for all languages
No label defined
    English
    The complete graph \(t\)-packings and \(t\)-coverings
    scientific article; zbMATH DE number 490741

      Statements

      The complete graph \(t\)-packings and \(t\)-coverings (English)
      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
      packings
      0 references
      coverings
      0 references
      edge-decomposition
      0 references
      multigraphs
      0 references
      complete bipartite graph
      0 references
      0 references

      Identifiers