Constructing the Spectrum for Packings of the Complete Graph with Trees That Have up to Five Edges

Abstract

The spectrum problem for decomposition of trees with up to eight edges was introduced and solved in 1978 by Huang and Rosa. Additionally, the packing problem was settled for all trees with up to six edges by Roditty. For the first time, we consider obtaining all possible leaves in a maximum tree-packing of $K_n$, which we refer to as the spectrum problem for packings of complete graphs. In particular, we completely solve this problem for trees with at most five edges. The packing designs are used in developing optimal error-correcting codes, which have applications in biology, such as in DNA sequencing.