Covering Designs with Minimum Overlap

Abstract

Let $H$ be a graph, and let $k$ be a positive integer. A graph $G$ is $H$-coverable with overlap $k$ if there is a covering of all the edges of $G$ by copies of $H$ such that no edge of $G$ is covered more than $k$ times. The number $ol(H,G)$ is the minimum $k$ for which $G$ is $H$-coverable with overlap $k$.

It is established (Theorem 2.1) that if $n$ is sufficiently large then
$$ol(H,K_n)\le 2.$$

For $H$ being a path, a matching or a star it is enough to assume $|H|\le n$ (Theorem 3.1).

The same result is obtained (Main Theorem) for any graph $H$ having at most four vertices, or else at most four edges with a single exception $ol(K_4,K_5)=3$.