Let H=(V-II, E-II) be a graph, and let k be a positive integer. A grap
h G = (V-G, E-G) is H-coverable with overlap k if there is a covering
of the edges of G by copies of H such that no edge of G is covered mor
e than k times. Denote by overlap(H, G) the minimum k for which G is H
-coverable with overlap k. The redundancy of a covering that uses t co
pies of H is (t\E-II\-\E-G\)/\E-G\. Our main result is the following:
If H is a tree on h vertices and G is a graph with minimum degree delt
a(G)greater than or equal to(2h)(10)+C, where C is an absolute constan
t, then overlap(H,G)less than or equal to 2. Furthermore. one can find
such a covering with overlap 2 and redundancy at most 1.5\delta(G)(0.
1). This result is tight in the sense that for every tree H on h great
er than or equal to 4 vertices and for every function f, the problem o
f deciding if a graph with delta(G)greater than or equal to f(h) has o
verlap( H, G)=1 is NP-complete. (C) 1997 Academic Press.