Isomorphic factorization of regular graphs of even degree

Journal of the Australian Mathematical Society

M. N Ellingham¹ 

关键词: 05 C 70;   

DOI  :  10.1017/S1446788700032183

学科分类：数学（综合）

来源: Cambridge University Press

【 摘 要 】

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.

【 授权许可】

Unknown