Decomposition of complete graphs into small graphs

Abstract

In 1967, A. Rosa proved that if a bipartite graph $G$ with $n$ edges has an $\alpha$-labeling, then for any positive integer $p$ the complete graph $K_{2np+1}$ can be cyclically decomposed into copies of $G$. This has become a part of graph theory folklore since then. In this note we prove a generalization of this result. We show that every bipartite graph $H$ which decomposes $K_{k}$ and $K_{m}$ also decomposes $K_{km}$.