Two problems on butterfly graphs

The cycle partition problem and the pancycle problem on butterfly graphs are studied in this paper. Suppose G=(V,E) is a graph and {V₁,V₂,...,V_s} is a partition of V. We say that {V₁,V₂,...,V_s} forms a cycle partition of G if each subgraph of G induced by V₁ contains a cycle of length |V_i|, where 1⩽i⩽s. A cycle partition {V₁,V₂,...,V_s} is λ-uniform if |V₁|=|V₂|=...=|V_s|=λ. G has λ-complete uniform cycle partitions if G has mλ-uniform cycle partitions for all 1⩽m⩽(r+n)/2 and m dividing |V|/λ. Let BF(k,r) denote the r-dimensional k-ary butterfly graph. For the cycle partition problem, we construct a lot of uniform cycle partitions for BF(k,r). Besides, we construct r-complete uniform cycle partitions for BF(2,r), and kr-complete uniform cycle partitions for BF(k,r). For the pancycle problem, given any pair of n and r we can determine if there exists a cycle of length n in BF(2,r), and construct it if it exists. The results of this paper reveal that the butterfly graphs are superior in embedding rings. They can embed rings of almost all possible lengths. Besides, there are many situations in which they can embed the most rings of the same length