Decompositions of Graphs into 5-Cycles and Other Small Graphs

Abstract

In this paper we consider the problem of finding the smallest number $q$ such that any graph $G$ of order $n$ admits a decomposition into edge disjoint copies of a fixed graph $H$ and single edges with at most $q$ elements. We solve the case when $H$ is the 5-cycle, the 5-cycle with a chord and any connected non-bipartite non-complete graph of order 4.