COVERING THE EDGES OF A GRAPH BY A PRESCRIBED TREE WITH MINIMUM OVERLAP

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.