Opuscula Math. 30, no. 3 (2010), 277-280
http://dx.doi.org/10.7494/OpMath.2010.30.3.277

Opuscula Mathematica

# Decomposition of complete graphs into small graphs

Dalibor Froncek

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}$$.

Keywords: graph decomposition, graph labeling.

Mathematics Subject Classification: 05C78.

Full text (pdf)

• Dalibor Froncek
• University of Minnesota, Duluth, Department of Mathematics and Statistics, 1117 University Dr., Duluth, MN 55812, U.S.A.