Covering the edges of a graph by a prescribed tree with minimum overlap

Noga Alon, Yair Caro, Raphael Yuster

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

LetH=(VH,EH) be a graph, and letkbe a positive integer. A graphG=(VG,EG) 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|EH|-|EG|)/|EG|. 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 languageEnglish (US)
Pages (from-to)144-161
Number of pages18
JournalJournal of Combinatorial Theory. Series B
Volume71
Issue number2
DOIs
StatePublished - Nov 1 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'Covering the edges of a graph by a prescribed tree with minimum overlap'. Together they form a unique fingerprint.

  • Cite this