Minimum Coverings of the Complete Graph with 5-cycles

Abstract

Let $K_v$ be the complete graph on $v$ vertices, and $C_5$ be a cycle of length five. A simple minimum $(v,C_5,1)$-covering is a pair $(V,C)$ where $V=V(K_v)$ and $C$ is a family of edge-disjoint 5-cycles of minimum cardinality which partition $E(K_v)\cup E$, for some $E\subset E(K_v)$. The collection of edges $E$ is called the excess. In this paper, we determine the necessary and sufficient conditions for the existence of a simple minimum $(v,C_5,1)$-covering. More precisely, for each $v\ge 6$, we prove that there is a simple minimum $(v,C_5,1)$-covering having all possible excesses.