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
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