J Austral Math Soc Ser A 44 pp402--420, 1988.

Isomorphic Factorization of Regular Graphs of Even Degree

M. N. Ellingham

Abstract

A graph G is divisible by t if its edge set can be partitioned into t subsets, such that the subgroups (called factors) induced by the subsets are all isomorphic. Such an edge partition is an isomorphic factorization. It is proved that a 2k-regular graph with an even number of vertices is divisible by 2k provided it contains either no 3-cycles or no 5-cycles. It is also shown that any 4-regular graph with an even number of vertices is divisible by 4. In both cases the components of the factors found are paths of length 1 and 2, and the factorizations can be constructed in polynomial time.

1980 AMS Subject Classification: 05C70

Browse the article

Authors

M. N. Ellingham

Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada.

(Current address: Department of Mathematics, Vanderbilt University, Nashville, Tennessee 37235, U.S.A.)