## Abstract

LetH=(V_{H},E_{H}) be a graph, and letkbe a positive integer. A graphG=(V_{G},E_{G}) isH-coverable with overlap kif there is a covering of the edges ofGby copies ofHsuch that no edge ofGis covered more thanktimes. Denote by overlap(H,G) the minimumkfor whichGisH-coverable with overlapk. Theredundancyof a covering that usestcopies ofHis (t|E_{H}|-|E_{G}|)/|E_{G}|. Our main result is the following: IfHis a tree onhvertices andGis a graph with minimum degreeδ(G)≥(2h)^{10}+C, whereCis an absolute constant, then overlap(H,G)≤2. Furthermore, one can find such a covering with overlap 2 and redundancy at most 1.5/δ(G)^{0.1}. This result is tight in the sense that for every treeHonh≥4 vertices and for every functionf, the problem of deciding if a graph withδ(G)≥f(h) has overlap(H,G)=1 is NP-complete.

Original language | English (US) |
---|---|

Pages (from-to) | 144-161 |

Number of pages | 18 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 71 |

Issue number | 2 |

DOIs | |

State | Published - Nov 1997 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics