Multidecomposition of complete graphs into cycles and claws

Source 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 $\alpha$ and $\beta$ and any positive integer $n \geq 6$, there exists a decomposition of $K_n$ into $\alpha$ copies of $C_6$ and $\beta$ copies of $S_3$ if and only if $6\alpha + 3\beta = \binom{n}{2}$, $\beta \neq 1,2$ when $n$ is odd, and $\beta \geq \left\lceil \frac{n}{4} \right\rceil$ when $n$ is even. Received: 30 Dec 2022 | Accepted: 05 June 2025