Packing the Crowns with Cycles and Stars

Abstract

Let $F,G$ and $H$ be graphs. A $(G,H)$-decomposition 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$. For $L\subseteq F$, a $(G,H)$-packing of $F$ with leave $L$ is a $(G,H)$-decomposition of $F–E(L)$. A $(G,H)$-packing of $F$ with the largest cardinality is a maximum $(G,H)$-packing. This paper gives the solution of finding the maximum $(C_k,S_k)$-packing of the crown $C_{n,n-1}$.