The complete graph \(t\)-packings and \(t\)-coverings (Q1313352): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 12:51, 31 January 2024
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