On the cyclic decomposition of complete graphs into bipartite graphs

Abstract

Let G be a graph with n edges. It is known that there exists a cyelic Gdecomposition of K 2n+1 if and only if G has a ρ-Iabeling. An α-labeling of G easily yields both a cyelic G-decomposition of Kn,n and of K2nx+l for all positive integers x. It is well-known that certain classes of bipartite graphs (including certain trees) do not have α-Iabelings. Moreover, there are bipartite graphs with n edges which do not cyclically divide Kn,n. In this article, we introduce the concept of an ordered ρ-labeling (denoted by ρ+) of a bipartite graph, and prove that if a graph G with n edges has a ρ+ -labeling, then there is a cyclic G-decomposition of K 2nx+1 for all positive integers x. We also introduce the concept of a θ-labeling which is a more restrictive ρ+ -labeling. We conjecture that all forests have a ρ+labeling and show that the vertex-disjoint union of any finite collection of graphs that admit α-labelings admits a θ-labeling.