Efficient Covering Designs of the Complete Graph

Yair Caro, Raphael Yuster

Abstract


Let $H$ be a graph. We show that there exists $n_0=n_0(H)$ such that for every $n \geq n_0$, there is a covering of the edges of $K_n$ with copies of $H$ where every edge is covered at most twice and any two copies intersect in at most one edge. Furthermore, the covering we obtain is asymptotically optimal.


Full Text: PDF