Article contents
Isomorphic factorization of regular graphs of even degree
Published online by Cambridge University Press: 09 April 2009
Abstract
A graph G is divisible by t if its edge set can be partitioned into t subsets, such that the subgraphs (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 divisble 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.
MSC classification
- Type
- Research Article
- Information
- Copyright
- Copyright © Australian Mathematical Society 1988
References
- 2
- Cited by