Decomposition of Graphs into Cycles of Length Seven and Single Edges

Abstract

Given graphs $G$ and $H$, an $H$-decomposition of $G$ is a partition of the edge set of $G$ such that each part is either a single edge or forms a graph isomorphic to $H$. Let ${\gamma }_H(n)$ denote the smallest number $k$ such that any graph $G$ of order $n$ admits an $H$-decomposition with at most $k$ parts. Here, we study the case when $H=C_7$, the cycle of length $7$, and prove that ${\gamma }_{C_7}(n)=\lceil \frac{n{Z}^2}{4}\rceil$ for all $n\ge 10$.