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
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.
- Dalibor Froncek
- University of Minnesota, Duluth, Department of Mathematics and Statistics, 1117 University Dr., Duluth, MN 55812, U.S.A.
- Received: 2010-01-21.
- Accepted: 2010-03-26.
