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.

Published
1997-02-03
Article Number
R10