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

Noga Alon; Yair Caro; Raphael Yuster

doi:10.1006/jctb.1997.1768

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

Noga Alon, Yair Caro, Raphael Yuster

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

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)¹⁰+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	https://doi.org/10.1006/jctb.1997.1768
State	Published - Nov 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jctb.1997.1768

Cite this

@article{f1e64e13517945c89a604e618eadc535,

title = "Covering the edges of a graph by a prescribed tree with minimum overlap",

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.",

author = "Noga Alon and Yair Caro and Raphael Yuster",

note = "Funding Information: * Research supported in part by the Fund for Basic Research administered by the Israel Academy of Sciences.",

year = "1997",

month = nov,

doi = "10.1006/jctb.1997.1768",

language = "English (US)",

volume = "71",

pages = "144--161",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

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

AU - Alon, Noga

AU - Caro, Yair

AU - Yuster, Raphael

N1 - Funding Information: * Research supported in part by the Fund for Basic Research administered by the Israel Academy of Sciences.

PY - 1997/11

Y1 - 1997/11

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0031280922

UR - https://www.scopus.com/inward/citedby.url?scp=0031280922&partnerID=8YFLogxK

U2 - 10.1006/jctb.1997.1768

DO - 10.1006/jctb.1997.1768

M3 - Article

AN - SCOPUS:0031280922

SN - 0095-8956

VL - 71

SP - 144

EP - 161

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 2

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this