We examine decompositions of complete graphs K4 k + 2 into 2 k + 1 isomorphic spanning trees. We develop a method of factorization based on a new type of vertex labelling, namely blended ρ-labelling. We also show that for every k ≥ 1 and every d, 3 ≤ d ≤ 4 k + 1 there is a tree with diameter d that decomposes K4 k + 2 into 2 k + 1 factors isomorphic to T.
Bibliographical noteFunding Information:
Research for this article was supported by the University of Minnesota Duluth Grant 177–1009.
- Graph factorization
- Graph labelling
- Spanning trees