Covering the edges of a graph by a prescribed tree with minimum overlap
type: Item
instance of: scholarly article
title: Covering the edges of a graph by a prescribed tree with minimum overlap
zbMATH Open document ID: 0906.05053
author: Noga Alon
author: Yair Caro
author: Raphael Yuster
published in: Journal of Combinatorial Theory. Series B
publication date: 1999-02-01T00:00:00Z
review text: Let \(H\) be a graph, and let \(k\) be a positive integer. If there is a covering of a graph \(G\) by copies of \(H\) such that no edge of \(G\) is covered more than \(k\) times, then \(G\) is said to be \(H\)-coverable with overlap \(k\). The minimum \(k\) for which \(G\) is \(H\)-coverable with overlap \(k\) is denoted by overlap\((H,G)\). We define the redundancy of a covering which uses \(t\) copies of \(H\) as \((t| E_H| -| E_G|)/ | E_G| \). The authors show that if \(H\) is a tree of order \(h\) and \(G\) is a graph with minimum degree \(\delta(G) \geq (2h)^{10}+ C\), where \(C\) is an absolute constant, then overlap\((H,G)\) is at most 2. They further show that such a covering with overlap 2 and redundancy at most \(1.5/(\delta(G))^{0.1}\) can be found. The authors also prove that for every tree \(H\) of order at least 4 and for every function \(f\), the problem of deciding if a graph \(G\) with minimum degree at least \(f(h)\) has overlap\((H,G)=1\) is NP-complete.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1154571
zbMATH Keywords: covering
zbMATH Keywords: overlap
zbMATH Keywords: NP-complete
reviewed by: Michael Raines
MaRDI profile type: Publication
full work available at URL: jctb.1997.1768
OpenAlex ID: W2095046926
cites work: Q5422499
cites work: Q4198056
cites work: Q4083463
DOI: 10.1006/JCTB.1997.1768
description: scientific article; zbMATH DE number 1154571