Packings in Complete Graphs

Lorenz Halbeisen1, Norbert Hungerbiihler2
1 Mathematik Departement ETH Zentrum HG G33.5 CH-8092 Ziirich (Switzerland)
2 Mathematisches Institut Universitat Freiburg Rheinstr. 10 D-79104 Freiburg (Germany)

Abstract

We deal with the concept of packings in graphs, which may be regarded as a generalization of the theory of graph design. In particular, we construct a vertex- and edge-disjoint packing of \(K_n\) (where \(\frac{n}{2} \mod 4\) equals 0 or 1) with edges of different cyclic length. Moreover, we consider edge-disjoint packings in complete graphs with uniform linear forests (and the resulting packings have special additional properties). Further, we give a relationship between finite geometries and certain packings which suggests interesting questions.