Cycles in butterfly graphs

Three problems in connection with cycles on the butterfly graphs are studied in this paper. The first problem is to construct complete uniform cycle partitions for the butterfly graphs. Suppose that G = (V, E) is a graph. A partition {V1, V2, ..., Vs} of V is said to be a uniform cycle partition of G if |V1| = |V2| = · · · = |Vs | and each subgraph of G induced by Vi contains a cycle of length |Vi |, where 1 ≤ i ≤ s. We say that G has λ-complete uniform cycle partitions if G has uniform cycle partitions whose cycle lengths include all possible multiples of λ. The second problem is to determine if there exists a cycle of length n in the butterfly graphs, where n is arbitrarily given. The third problem is to establish Hamiltonian cycles in faulty butterfly graphs. The results of this paper reveal that the butterfly graphs are superior in embedding rings. © 2000 John Wiley & Sons, Inc.