Multidecompositions of Complete Bipartite Graphs into Cycles and Stars

Abstract

Let $C_k$ denote a cycle of length $k$ and let $S_k$ denote a star with $k$ edges. For graphs $F$, $G$, and $H$, a $(G,H)$-multidecomposition of $F$ is a partition of the edge set of $F$ into copies of $G$ and copies of $H$ with at least one copy of $G$ and at least one copy of $H$. In this paper, necessary and sufficient conditions for the existence of the $(C_k,S_k)$-multidecomposition of a complete bipartite graph are given.