Multidecomposition of complete graphs into cycles and claws

Abstract

Let C_n and S_n respectively denote a cycle and star with n edges. Let K_n denote a complete graph on n vertices. In this paper, it is shown that for any non-negative integers α and β and any positive integer n ≥ 6, there exists a decomposition of K_n into α copies of C₆ and β copies of S₃ if and only if

6α + 3β = n(n − 1) 2

β ≠ 1, 2 when n is odd, and β ≥ ⌈n/4⌉ when n is even.