Covering Designs with Minimum Overlap

Y. Caro1, Y. Roditty2, J. Schénheim2
1Department of Mathematics School of Education University of Haifa – Oranim Tivon Isreal 36006
2School of Mathematical Sciences Tel-Aviv University Ramat-Aviv, Tel-Aviv Isreal 69978

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) \leq 2.\]

For \(H\) being a path, a matching or a star it is enough to assume \(|H| \leq 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\).